Технология цифровой связи (стр. 11 из 14)
Циклические коды. Важным подклассом линейных блочных кодов являются двоичные циклические коды (cycliccodes). Код легко реализуется на регистре сдвига с обратной связью; на подобных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая структура циклического кода естественным образом позволяет эффективно реализовать методы декодирования. Итак, линейный код (n, к) называется циклическим, если он обладает следующим свойством. Если n-кортеж U= (u0, u1, и2, …, un-1) является кодовым словом в подпространстве S, тогда U(1)= (un-1,u0, u1, и2,..., un-1), полученный из U с помощью циклического сдвига, также является кодовым словом в S. Или, вообще, U(i) = (un-i;. un-i+1,…, un-1,u0, u1,…un-i-1), полученный i циклическими сдвигами, является кодовым словом в S.
Циклический код Файра.Циклические коды, обнаруживающие и исправляющие пакеты ошибок (коды Файра). Под пакетом ошибок длиной b понимают такой вид комбинации помехи, в которой между крайними разрядами, пораженными помехами, содержится b-2разряда. Например, при b=5 комбинации помехи, т.е. пакет ошибок, могут иметь следующий вид: 10001 (поражены тоько два крайних символа), 11111 (поражены все символы), 10111, 11101, 11011 (не поражен лишь один символ), 10011, 11001, 10101 (поражены три символа). При любом варианте непременным условием пакета данной длины является поражение крайних символов.
Коды Файра могут исправлять пакет ошибок длиной b и обнаруживать пакет ошибок длиной b [заметим, что в кодах Файра понятие кодового расстояния - d].
Коды Боуза-Чоудхури-Хоквингэма. 
. Эти коды, разработанные Боузом, Чодхури и Хоквинхемом (сокращенно коды БЧХ), позволяют обнаруживать и исправлять любое число ошибок. Заданными при кодировании является число ошибок s, которое следует исправить, и общее число символов, посылаемых в линию, т.е. длина слов n. Числа информационных символов k и контрольных символов m,а также состав контрольных символов подлежат определению.
Коды БЧХ для обнаружения ошибок. Их строят следующим образом. Если необходимо образовать код с обнаружением четного числа ошибок, то по заданному числу rнаходят значения dи s. Дальнейшее кодирование выполняют, как и ранее. Если требуются обнаружить нечетное число ошибок, то находят ближайшее меньшее целое число s и кодирование производят так же, как и в предыдущем случае: образующий многочлен дополнительно умножают на двучлен 
. Например, требуются построить код обнаруживающий семь ошибок при n=15. Находим, что d=8, а ближайшее меньшее значение s=3. Далее определяем многочлен 
, как указано в примере 3.5, и умножаем его на двучлен 
, т.е. получаем 
. Таким образом построен код БЧХ(15,4).
11Лекция №11. Помехоустойчивые коды и методы декодирования корректирующих кодов
Цель лекции: изучение помехоустойчивых кодов и методов декодирования корректирующих кодов
Содержание:
а) коды Рида- Соломона;
б) сверточные коды;
в)классификация корректирующих кодов;
г) методы декодирования корректирующих кодов.
11.1 Коды Рида- Соломона
Коды Рида-Соломона (Reed-Solomoncode, R-Scode) — это недвоичные циклические коды, символы которых представляют собой m-битовые последовательности, где т — положительное целое число, большее 2. Код (n,к) определен на m-битовых символах при всех n и k, для которых
(11.1)
где k - число информационных битов, подлежащих кодированию, а n - число кодовых символов в кодируемом блоке. Для большинства сверточных кодов Рида-Соломона (n, к)
(11.2)
где t - количество ошибочных битов в символе, которые может исправить код, а n-k = 2t- число контрольных символов. Расширенный код Рида-Соломона можно получить при n = 2m или n= 2m+ 1, но не более того.
Код Рида-Соломона обладает наибольшим минимальным расстоянием, возможным для линейного кода с одинаковой длиной входных и выходных блоков кодера. Для недвоичных кодов расстояние между двумя кодовыми словами определяется (по аналогии с расстоянием Хэмминга) как число символов, которыми отличаются последовательности. Для кодов Рила-Соломона минимальное расстояние определяется следующим образом.
(11.3)
Сверточные коды. Особенностью линейного блочного кода, который описывается двумя целыми числами, n и k, и полиномиальным или матричным генератором является то, что каждый из n-кортежей кодовых слов однозначно определяется k-кортeжeм входного сообщения. Целое число к указывает на число бит данных, которые образуют вход блочного кодера. Целое число п - это суммарное количество разрядов в соответствующем кодовом слове на выходе кодера. Отношение k/n, называемое степенью кодирования кода (coderate), является мерой добавленной избыточности. Сверточный код описывается тремя целыми числами n, k и К, где отношение k/n имеет такое же значение степени кодирования (информация, приходящаяся на закодированный бит), как и для блочного кода; однако п не определяет длину блока или кодового слова, как это было в блочных кодах. Целое число К является параметром, называемым длиной кодового ограничения (constrain! length); оно указывает число разрядов k-кортежа в кодирующем регистре сдвига. Важная особенность сверточных кодов, в отличие от блочных, состоит в том, что кодер имеет память - n-кортежи, получаемые при сверточном кодировании, являются функцией не только одного входного k-кортежа, но и предыдущих К-1 входных k-кортежей. На практике nи к - это небольшие целые числа, а К изменяется с целью контроля мощности и сложности кода.
Методы декодирования корректирующих кодов. Существует несколько вариантов декодирования циклических кодов. Один из них заключается в следующем:
1.Числение остатка (синдрома). Принятую комбинацию делят на образующий многочлен Р(Х). Остаток R(X)=0 означает, что комбинации принята без ошибок;
2.Подсчет веса остатка W. Если вес остатка равен или меньше числа исправляемых ошибок, т.е. W≤s, то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию;
3.Циклический сдвиг на один символ влево. Если W>s, то производят циклический сдвиг влево и полученную комбинацию снова делят на образующий многочлен. Если вес остатка W≤s , то циклически сдвинутую комбинацию складывают с остатком и затем циклически сдвигают ее в обратную строну вправо на один символ. В результате получают исправленную комбинацию;
4.Дополнительные циклические сдвиги влево. Если после циклического сдвига на один символ по-прежнему W>s, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига сдвинутую комбинацию делят на Р(Х) и проверяют вес остатка. При W≤s выполняют действия, указанные в п.3, с той лишь разницей, что обратных циклических сдвигов вправо делают столько, сколько их было сделано влево.
Метод проверки на четность. Если комбинация принята без искажения, то сумма единиц по модулю 2 даст нуль. При искажении какого – либо символа суммирование при проверке может дать единицу. По результату суммирования каждой из проверок составляют двоичное число, указывающее на место искажения.
Мягкое и жесткое декодирование.Для двоичной кодовой системы со степенью кодирования 1/2 демодулятор подает на декодер два кодовых символа за раз. Для жесткого (двухуровневого) декодирования каждую пару принятых кодовых символов можно изобразить на плоскости в виде одного из углов квадрата. Углы помечены двоичными числами (0, 0), (0, 1), (1, 0) и (1, 1), представляющими четыре возможных значения, которые могут принимать два кодовых символа в жесткой схеме принятия решений. Аналогично для 8-уровневого мягкого декодирования каждую пару кодовых символов можно отобразить на плоскости в виде равностороннего прямоугольника размером 8x8, состоящего из 64 точек. В этом случае демодулятор больше не выдает жестких решений; он выдает квантованные сигналы с шумом (мягкая схема принятия решений).
Основное различие между мягким и жестким декодированием по алгоритму Витерби состоит в том, что в мягкой схеме не используется метрика расстояния Хэмминга, поскольку она имеет ограниченное разрешение.
Мажоритарное декодирование. Этот метод заключается в многократной проверке каждого символа принятой кодовой комбинации по специальным таблицам коэффициентов, составленным для каждого варианта (n, k) циклического кода. Значение каждого символа определяется по мажоритарному принципу (слово «мажоритарный» означает большинство), т.е. по принципу голосования. Это означает, что если, например, один из пяти проверок данного символа три показали 1, а две- 0, то символу присваивается значение 1. Если все проверки показали 1 или 0, то символ считается неискаженным и принимается без изменения.
Если при какой-либо проверке окажется равное число 1 и 0, то это означает, что для данного кода произошла неисправимая комбинация ошибок и принятая комбинация должна быть забракована.