. Кодовое расстояние и корректирующая способность кода

Размещено на http://www.allbest.ru/

Основные принципы обнаружения и исправления ошибки. Кодовое расстояние и корректирующая способность кода. Коды Хемминга



От СПДС обычно требуется не только передавать сообщения с заданной скоростью передачи информации, но и обеспечивать при этом требуемую достоверность.

Помехи, действующие в канале, как известно, приводят к возникновению ошибок. Исходная вероятность ошибки в каналах связи обычно не позволяет достичь высокой степени достоверности без применения дополнительных мероприятий. К таким мероприятиям, обеспечивающим защиту от ошибок, относят применения корректирующих кодов.

В общей структурной схеме СПДС задачу защиты от ошибок выполняет кодер и декодер канала, который иногда называют УЗО.

Понятие о корректирующих кодах

Пусть имеется источник сообщений с объемом алфавита К.

Поставим в соответствие каждому сообщению n - элементную двоичную последовательность. Всего последовательностей из n - элементов может быть .

Если , то все последовательности (или кодовые комбинации) будут использоваться для кодирования сообщений, т.е. будут разрешенными.

Полученный таким образом код называется простым, он не способен обнаруживать и исправлять ошибки.

Для того, что бы код мог обнаруживать и исправлять ошибки необходимо выполнение условия , при этом неиспользуемые для передачи комбинации (N₀-K) называют запрещенными.

Появление ошибки в кодовой комбинации будет обнаружено, если передаваемая разрешенная комбинация перейдет в одну из запрещенных.

Расстояние Хемминга - характеризует степень различия кодовых комбинаций и определяется числом несовпадающих в них разрядов.

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d₀.

Минимальное расстояние d₀ - называется кодовым расстоянием

Кодовое расстояние определяет способность кода обнаруживать и исправлять ошибки.

У простого кода d₀=1 - он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В общем случае справедливы следующие соотношения

для обнаруживающей способности:

для четных

для исправляющей способности

для нечетных

Коды Хемминга

ошибка корректирующий код хемминг

Кодом Хемминга называется групповой (n,k) код, исправляющий одиночные ошибки и обнаруживающий двукратные ошибки.

Для построения кода, обеспечивающего передачу К сообщений и исправление t-кратной ошибки требуется:

Найти число информационных разрядов k и кодовое расстояние d₀

Построить производящую матрицу на основе единичной матрицы путем добавления проверочных разрядов по следующим правилам:

Число единиц среди дописываемых элементов должно быть не менее d₀ -1

Группы дописанных элементов должны отличаться друг от друга не менее, чем в d₀ - 2 элементах.

После построить проверочную матрицу. Для построения проверочной матрицы транспонируем подматрицу, содержащуюся в производящей матрице. По столбцам этой матрицы можно будет в дальнейшем определить, в каком элементе во время передачи произошла ошибка.

Классификация кодов

Помехоустойчивые коды делятся на блочные и непрерывные коды. К блочным кодам относятся коды, в которых каждому сообщению отводится блок из n символов (разрядов) или блоки с разным числом символов. В связи с этим блочные коды делятся на равномерные и неравномерные коды. Широкое практическое применение нашли равномерные коды. К неравномерным кодам относится, например, код Морзе. Непрерывные коды, к которым относятся рекуррентные (свёрточные), представляют собой непрерывные последовательности единичных элементов, не разделенные на блоки. В таких кодах избыточные разряды помещаются в определенном порядке между информационными.

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

Нелинейные коды указанным выше свойством не обладают и применяются значительно реже. Примером несистематического кода является код с контрольным суммированием.

Различают два метода формирования проверочной группы: поэлементной и в целом; последний характерен для широко распространенных полиномиальных кодов (и их разновидности - циклических). Среди систематических кодов большое применение нашли коды Хэмминга. Эти коды, обеспечивающие d₀=3, позволяют исправить одну ошибку. Помехоустойчивые коды могут иметь основание (значность) и больше 2. Однако в связи со сложностью построения кодирующих и декодирующих устройств они на практике применяются значительно реже двоичных.

Рисунок 5.1. Классификация помехоустойчивых кодов

Линейные коды

Двоичный блочный код является линейным, если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Линейные коды также называют групповыми.

Понятие группы.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

1. Замкнутость g_ig _j= g_k G в результате операции с двумя элементами группы получается третий, так же принадлежащий этой группе.

2. Ассоциативность (сочетательность) (g_ig_j) g_k = g_i (g_j g_k)

3. Наличие нейтрального элемента g_j e = g_j

4. Наличие обратного элемента g_i (g_i)^-1= e

Если выполняется условие g_i g_j = g_j g_i, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

Поэтому, используя свойство замкнутости относительно операции 2, множество всех элементов можно задать не перечислением всех элементов, а производящей матрицей.

Все остальные элементы, кроме 0, могут быть получены путем сложения по модулю 2 строк производящей матрицы в различных сочетаниях.

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

Циклический код

Широкое распространение на практике получил класс линейных кодов, которые называются циклическими. Данное название происходит от основного свойства этих кодов: если некоторая кодовая комбинация принадлежит циклическому коду, то комбинация, полученная циклической перестановкой исходной комбинации (циклическим сдвигом), также принадлежит данному коду.



.

Вторым свойством всех разрешенных комбинаций циклических кодов является их делимость без остатка на некоторый выбранный полином, называемый производящим. Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином. В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементную кодовую комбинацию можно описать полиномом (n-1) степени, в виде

(7.1)

где a_i={0,1}, причем a_i=0 соответствуют нулевым элементам комбинации, а a_i=1 - ненулевым.

Действия над многочленами

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

,

Поскольку .

Следует отметить, что действия над коэффициентами полинома (сложение и умножение) производятся по модулю 2. Деление выполняется, как обычно, только вычитание заменяется суммированием по модулю два.

Отметим, что запись кодовой комбинации в виде многочлена, не всегда определяет длину кодовой комбинации.



Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

Пусть задан полином , определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

Умножаем многочлен исходной кодовой комбинации на

Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления, полученного в предыдущем пункте произведения на образующий полином

Окончательно разрешенная кодовая комбинация циклического кода определится так

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация - разрешенная, то остаток от деления будет нулевым.

Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Формирование базиса (производящей матрицы) циклического кода

Формирование базиса циклического кода возможно как минимум двумя путями.

Вариант первый.

Составить единичную матрицу для простого исходного кода.

Определить для каждой кодовой комбинации исходного кода группу проверочных элементов и дописать их в соответствующие строки матрицы.

Полученная матрица и будет базисом циклического кода. Причем, в данном случае, разрешенные комбинации заведомо разделимы (т.е. информационные и проверочные элементы однозначно определены).

Вариант второй.

Дописать слева от КК, соответствующей образующему полиному циклического кода нули так, чтобы длина разрешенной кодовой комбинации равнялась n.

Получить остальные разрешенные кодовые КК базиса, используя циклический сдвиг исходной. (В базисе должно быть k - строк). В данном случае код будет неразделимым.

Получив базис ЦК, можно получить все разрешенные комбинации, проводя сложение по модулю 2 кодовых комбинаций базиса в различных сочетаниях и плюс нулевая.



Построение кодера циклического кода

Разрешенная комбинация циклического кода образуется из комбинации простого (исходного) кода путем умножения ее на и прибавления остатка R(x) от деления на образующий полином .

Умножение полинома на одночлен - эквивалентно добавлению к двоичной последовательности соответствующей G(x) , r - нулей справа. Для реализации операции добавления нулей используется r-разрядный регистр задержки.

Процедура деления одного двоичного числа на другое сводится к последовательному сложению по mod2 делителя с соответствующими членами делимого, затем с двоичным числом, полученным в результате первого сложения, далее с результатом второго сложения и т.д., пока число членов результирующего двоичного числа не станет меньше числа членов делителя. Это двоичное число и будет остатком .

Построение формирователя остатка циклического кода

Структура устройства осуществляющего деление на полином полностью определяется видом этого полинома. Существуют правила позволяющие провести построение однозначно.

Сформулируем правила построения ФПГ.

Число ячеек памяти равно степени образующего полинома r.

Число сумматоров на единицу меньше веса кодирующей комбинации образующего полинома.

Место установки сумматоров определяется видом образующего полинома.

Сумматоры ставят после каждой ячейки памяти, (начиная с нулевой) для которой существует ненулевой член полинома. Не ставят после ячейки для которой в полиноме нет соответствующего члена и после ячейки старшего разряда.

4. В цепь обратной связи необходимо поставить ключ, обеспечивающий правильный ввод исходных элементов и вывод результатов деления.

Структурная схема кодера циклического кода

Полная структурная схема кодера содержит регистр задержки и формирователь проверочной группы.

Работа схемы для кодера (n, k)

1. На первом этапе К₁- замкнут К₂ - разомкнут. Идет одновременное заполнение регистров задержки и сдвига информационными элементами (старший вперед!) и через k-1 тактов старший разряд в последней ячейке (под номером k-1)

2. Во время k-го такта К₂ - замыкается, а К₁ - размыкается с этого момента в ФПГ формируется остаток. Одновременно из РЗ на выход выталкивается задержание информационные разряды.

За k тактов (с k по n включительно) в линию уйдут все k -информационных элемента. К этому времени в ФПГ сформируется остаток

3. К₂ - размыкается, К₁ - замыкается, и в след за информационными в линию уйдут элементы проверочной группы.

4. Одновременно идет заполнение регистров новой комбинацией.

Определение ошибочного разряда в ЦК

Пусть А(х) - многочлен соответствующий переданной кодовой комбинации. Н(х) - многочлен соответствующей принятой кодовой комбинацией. Тогда сложение данных многочленов по модулю два даст многочлен ошибки.



E(x)=A(x)H(x)

При однократной ошибке Е(х) будет содержать только один единственный член соответствующий ошибочному разряду.

Остаток - полученный от деления принятого многочлена H(x) на производящей P_r(x) равен остатку, полученному при делении соответствующего многочлена ошибок E(x) на P_r(x)

При этом ошибке в каждом разряде будет соответствовать свой остаток R(x) (он же синдром), а значит, получив синдром можно однозначно определить место ошибочного разряда.

Алгоритм определения ошибки

Пусть имеем n-элементные комбинации (n = k + r) тогда:

1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде, на образующей поленом P_r(x)

2. Делим полученный полином Н(х) на P_r(x) и получаем текущий остаток R(x).

3. Сравниваем R₀(x) и R(x).

- если они равны, то ошибка произошла в старшем разряде.

- если "нет", то увеличиваем степень принятого полинома на Х и снова проводим деления 

4. Опять сравниваем полученный остаток с R₀(x)

- если они равны, то ошибки во втором разряде.

- если нет, то умножаем Н(х)х² и повторяем эти операции до тех пор, пока R(X) не будет равен R₀(x).

Ошибка будет в разряде соответствующем числу на которое повышена степень Н(х) плюс один.

Выбор образующего полинома

В теории циклических кодов показано, что образующий полином представляет собой произведение так называемых минимальных многочленов m_i(x), являющихся простыми сомножителями (то есть делящимся без остатка лишь на себя и на 1) бинома xⁿ+ 1:

P(x)=m₁(x)* m₃(x)…m_j(x), (7.2)

где j = d₀ - 2 =( 2t_u.ош+1) - 2 = 2 t_и.ош - 1.

Существуют специальные таблицы минимальных многочленов, одна из которых приведена ниже. Кроме образующего полинома необходимо найти и количество проверочных разрядов r. Оно определяется из следующего свойства циклических кодов: для любых значений l и t_и.ош существует циклический код длины n =2^l - 1, исправляющий все ошибки кратности t_и.ош и менее, и содержащий не более проверочных элементов.

Так как , то откуда .



Очевидно, что для уменьшения времени передачи кодовых комбинаций, r следует выбирать как можно меньше.

После определения количества проверочных разрядов r, вычисления образующего полинома удобно осуществить, пользуясь таблицей минимальных многочленов, представленной в следующем виде:

Таблица 7.1 - Выбор образующего полинома

J=2tи.ош -1	Вид минимальных многочленов для
1	x2+x+1	x3+x+1	x4+x+1	x5+x+1	x6+x+1	x7+x+1
3	-	-	x4+x3+x2+x+1	x5+x4+x3+x2+1	x6+x4+x2+x+1	x7+x3+x2+x+1
5	-	-	-	x5+x4+x2+x+1	x6+x5+x2+x+1	x7+x4+x3+x2+1
7	-	-	-	-	x6+x3+1	х7+x6+x5+x4+x2+x+1

Определяя образующий полином, нужно из столбца для соответствующего соотношения выписать все многочлены, начиная с верхней строки до нижней с номером j=2t_и.ош-1 включительно. После этого следует перемножить выбранные минимальные многочлены в соответствии с (7.2).



Литература

Скляр Б. Цифровая связь. ? М., Санкт-П, Киев: Изд. дом «Вильямс», 2003.

Передача дискретных сообщений: Учебник для ВУЗов / В. П. Шувалов, Н. В. Захарченко, В. О. Шварцман и др.; Под ред. В. П. Шувалова. - М.: Радио и связь, 1990 - 464 с.

Теория электрической связи: Учебник для ВУЗов./ Зюко А.Г., Кловский Д.Д. - М:Радио и связь, 1999

Дополнительная литература:

Макаров А.А., Прибылов В.П. Помехоустойчивое кодирование: Монография/СибГУТИ - Новосибирск, 2005

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976.

Мирманов А.Б. Курс лекций по дисциплине «Технология цифровой связи» - Астана: КазАТУ, 2009. (электронный)

Размещено на Allbest.ru

...