Главная Блог Статьи Конференции Портфолио Flash-point RSS  RU EN

Владимир Бондаренко

Специалист по web-технологиям
ПОСЛЕДНИЕ ЗАПИСИ
  •  Тьма за спиной – мобильный квест написанный Виталием Зыковым
  •  Автоматизация процессов в компании: объединение всей информационной среды в одной системе Mauris CRM (CMS + SalesForce + MailChimp + мобильное приложение)
  •  10 советов по созданию страницы своей компании в «Википедии»
  •  Сравниваем форматы для документирования RESTful API: WADL, Swagger, I/O Docs, API BluePrint, RAML, Google API Discovery, Apimatic

  • ОБЛАКО ТЕГОВ
    Ajax Apple Chrome cloud CMS ECM Flash-point Folium iPad iPhone Java Script jQuery mobile development MVC PHP Python RESTful API SDK SEO StarCraft Swagger Twitter блоги видео кодирование конференция обучение SEO оцифровка информации плагины презентация программирование развлечение скрипт советы сравнение технологии хостинг ЧПУ
    КОНТАКТЫ

    Skype: coolweb_ua

    twitter

    СЧЕТЧИК


    Кодирование информации с применением кодов Рида-Соломона

    Кодирование информации с применением кодов Рида-Соломона

    Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации. Предупреждаю, что данный подход не будет рационален во многих случаях, но позволит реализовать помехоустойчивое кодирование данных с варьируемым процентом восстанавливаемой информации.

    При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных.  Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную:  n – 10, количество информационных символов; f – 3, количество восстанавливаемых символов;  g – 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2. Данные ходы компактнее кодов Хеминга на 1 символ.

    Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m,такое поле называется расширенным. GF(pm) – обозначение поля Галуа.

    Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 – 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.

    Подробно информацию о арифметике полей Галуа я опубликовал статью на Хабрахабр. В этой же статье пойдет речь о применений полей Галуа для кодирования, декодирования информации кодами Рида-Соломона.

    Для удобства подсчетов приведу 2 таблицы из статьи, посвященной полям Галуа.

     

    Таблица умножения

    Кодирование информации с применением кодов Рида-Соломона

     

    Таблица степеней

    Кодирование информации с применением кодов Рида-Соломона

    Перед началом кодирования мы определились с необходимым полем GF(q), где q=pm. Длина кодовой последовательности должна быть q-1. Таким образом, в нашем случае с GF(8) кодовая последовательность состоит из 7 элементов. Дальше нужно выяснить какие элементы будут информационными, а какие проверочные (избыточные). В самом начале мы говорили о том, что количество избыточных символов должно быть в два раза больше, чем то количество ошибочных символов, которое мы хотим восстановить. Если необходимо исправить двукратную ошибку (t=2 – кратность ошибки), то, соответственно, следует использовать четыре проверочных символа. Применим это к нашему примеру: из семи элементов для исправления двукратной ошибки необходимы четыре избыточных, а значит три информационных. Кодовая последовательность выглядит следующим образом:

    C=(c0, c1, c2, c3, c4, c5, c6), где c0, c1, c2 – информационные, c3, c4, c5, c6 – проверочные. 

    Хочу обратить внимание на тот факт, что исправление двукратной ошибки в кодовой последовательности из семи элементов означает, что можно бороться с ошибкой, вероятность возникновения которой не больше чем рош=2/7≈0,29. Если вероятность возникновения ошибки выше, то нужно увеличивать количество проверочных символов, иначе восстановить искаженную информацию все равно не получится. 

    Закодируем последовательность С=( 4, 6, 7, 0, 0, 0, 0), четыре последних символа – проверочные, равны нулю.

    Представим нашу последовательность в виде полинома:  

    С(x)=4∙x0+6∙x1+7∙x2+0∙x3+0∙x4+0∙x5+0∙x6=4+6∙x+7∙x2

    Кодирование осуществляется с помощью обратного дискретного преобразования Фурье (IDFT). Формула для кодирования: cj'=C(zj) , где z=2 – примитивный элемент поля.

    c0'=C(20 )=С(1)=4+6+7=5
    c1'=C(21 )=С(2)=4+6∙2+7∙4=4+7+1=2
    c2'=C(22 )=С(4)=4+6∙4+7∙6=4+5+4=5
    c3'=C(23 )=С(3)=4+6∙3+7∙5=4+1+6=3
    c4'=C(24 )=С(6)=4+6∙6+7∙2=4+2+5=3
    c5'=C(25 )=С(7)=4+6∙7+7∙3=4+4+2=2
    c6'=C(26 )=С(5)=4+6∙5+7∙7=4+3+3=4

    Получили закодированную последовательность:  C'=(5,2,5,3,3,2,4). В виде полинома: С(x)=5∙x0+2∙x1+5∙x2+3∙x3+3∙x4+2∙x5+4∙x6.

    Формула для декодирования cj =C' (z-j) .

    с0=C'(20 )=C'(1)=5+2+5+3+3+2+4=4
    с1=C' (2-1 )=C' (5)=5+2∙5+5∙7+3∙6+3∙3+2∙4+4∙2=5+1+6+1+5+3+3=6
    с2=C' (2-2 )=C' (7)=⋯=7
    с3=C' (2-3 )=C' (6)=⋯=0
    с4=C' (2-4 )=C' (3)=⋯=0
    с5=C' (2-5 )=C' (4)=⋯=0
    с6=C' (2-6 )=C' (2)=⋯=0

    При декодировании получили последовательность (4, 6, 7, 0, 0, 0, 0), которая соответствует исходной. Чтобы проверить не произошло ли искажение информации достаточно посмотреть на избыточные символы. Если они все еще равны нулю, то ошибки отсутствуют.

    Ошибка представляет собой другую последовательность, которая суммируется с закодированной. Допустим вектор ошибка имеет вид: f' =(0, 0, 5, 0, 3, 0, 0), тогда кодовая последовательность с ошибкой:

    Cf'=C'+f'=(5,2,0,3,0,2,4)

    Попробуем декодировать полученное кодовое слово: Cf'=5∙x0+2∙x1+0∙x2+3∙x3+0∙x4+2∙x5+4∙x6=5+2∙x1+3∙x3+2∙x5+4∙x6


    c0f=C'(20 )=C'(1)=5+2+0+3+0+2+4=2
    c0f=C'(2-1 )=C'(5)=5+2∙5+3∙6+2∙4+4∙2=5+1+1=5
    c0f=C'(2-2 )=C'(7)=5+2∙7+3∙2+2∙6+4∙4=5+5+6+7+6=7
    c0f=C'(2-3 )=C'(6)=5+2∙6+3∙7+2∙5+4∙3=5+7+2+1+7=6
    c0f=C'(2-4 )=C'(3)=5+2∙3+3∙4+2∙2+4∙6=5+6+7+4+5=5
    c0f=C'(2-5 )=C'(4)=5+2∙4+3∙5+2∙3+4∙7=5+3+4+6+1=5
    c0f=C'(2-6 )=C'(2)=5+2∙2+3∙3+2∙7+4∙5=5+4+5+5+2=3

     Cf=(2, 5, 7, 6, 5, 5, 3) – декодированная последовательность. Как видим, последние четыре элемента не равны нулю, что, собственно, и свидетельствует о наличии ошибки. Для исправления ошибки в первую очередь необходимо определить позиции искаженных символов. Для этого необходимо вычислить полином локаторов ошибок, корни которого и указывают на позиции ошибок. В матричном виде полином локаторов ошибок выглядит как L=[1, l1, l2, … lt]. Так как в нашем примере мы хотим исправить ошибку кратности 2, то L=[1, l1, l2].

    Выпишем последние четыре символа – синдром ошибки:

    6

    5

    5

    3

    S0

    S1

    S2

    S3

    Из них сформируем матрицу и вектор-столбец, необходимый для вычисления L. В общем виде:

    Кодирование информации с применением кодов Рида-Соломона

    В нашем примере:

    Кодирование информации с применением кодов Рида-Соломона

    Вычислим M-1, с учетом того, что мы работаем с арифметикой поля Галуа 

    Кодирование информации с применением кодов Рида-Соломона

    На всякий случай можно проверить правильность вычислений:

    Кодирование информации с применением кодов Рида-Соломона

    Итак:

    Кодирование информации с применением кодов Рида-Соломона

    Запишем L в виде полинома:

    L(x)=1+4x+2x2

    Вычислим корни полученного полинома простым перебором:

    L(20 )=L(1)=1+4+2=7
    L(21 )=L(2)=1+4∙2+2∙4=1
    L(22 )=L(4)=1+4∙4+2∙6=1+6+7=0
    L(23 )=L(3)=1+4∙3+2∙5=1+7+1=7
    L(24 )=L(6)=1+4∙6+2∙2=1+5+4=0
    L(25 )=L(7)=1+4∙7+2∙3=1+1+6=6
    L(26 )=L(5)=1+4∙5+2∙7=1+2+5=2

    Получили, что ошибки присутствуют в c2' и c4'.

    Теперь необходимо найти правильные значения. Для начала приведем L(x) к нормальному виду:

    L(x)=1+4x+2x2 |*5

    L(x)=x2+2x+5

    Запишем вектор ошибки (последние 4 символа – значения синдрома).  На местах информационных символов – знаки вопроса, их и необходимо вычислить.

    ?

    ?

    ?

    6

    5

    5

    3

    f0

    f1

    f2

    f3

    f4

    f5

    f6

    Осуществим свертку для f0, f1, f2, а затем вычислим их значения:

    Кодирование информации с применением кодов Рида-Соломона

    Получили F=(6, 3, 0, 6, 5, 5, 3), так как ошибка суммировалась с закодированной последовательностью, то произведем операцию кодирования над F:

    F(x)=6+3x+6x3+5x4+5x5+3x6

    Так как мы уже знаем позиции ошибок, то достаточно вычислить только f2'=F(22) и f4'=F(24) , все остальные будут равны нулю. Но для того чтобы точно в этом убедится честно посчитаем все значения:

    f0'=F(20)=F(1)=6+3+6+5+5+3=0
    f1'=F(21)=F(2)=6+3∙2+6∙3+5∙6+5∙7+3∙5=6+6+1+3+6+4=0
    f2'=F(22)=F(4)=6+3∙4+6∙5+5∙2+5∙3+3∙7=6+7+3+1+4+2=5
    f3'=F(23)=F(3)=6+3∙3+6∙4+5∙7+5∙2+3∙6=6+5+5+6+1+1=0
    f4'=F(24)=F(6)=6+3∙6+6∙7+5∙4+5∙5+3∙3=6+1+4+2+7+5=3
    f5'=F(25)=F(7)=6+3∙7+6∙2+5∙5+5∙6+3∙4=6+2+7+7+3+7=0
    f6'=F(26)=F(5)=6+3∙5+6∙6+5∙3+5∙4+3∙2=6+4+2+4+2+6=0

    Получили f' =(0, 0, 5, 0, 3, 0, 0). Сложим вектор ошибки с искаженной кодовой последовательностью:

    C'=Cf'+f'=(5,2,0,3,0,2,4)+(0,0,5,0,3,0,0)=(5,2,5,3,3,2,4)

    В результате получили правильную закодированную последовательность, при декодировании которой получим правильные информационные символы.


    Теги:  кодирование

    Читать по теме:

    loading

    Написать комментарий

    Имя:
    Почта (скрыта):
    Сайт:
    Текст: :) :( 0_o =-0 =-D 8-) :-(( TT >:o ]:->

    Использование любых материалов сайта возможно только при размещении активной и прямой ссылки на VBond.Kiev.ua.

    Главная | Блог | Статьи | Конференции | Портфолио | Flash-point | RSS

    developed by Bondarenko Volodymyr