ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
99. Дорожка с номером АА служит в качестве выводной зоны. Спиральный трек совершает 22188 оборотов по кругу CD, проходя примерно шестьсот оборотов на миллиметр при движении в направлении края диска Второе – именно на поликарбонате, в прямом смысле этого слова, печатается информация с матрицы — будь то фильм, музыка или программы. Естественно, что поликарбонат и лак прозрачны для лазерного излучения, поэтому «напечатанную» информацию для лазера необходимо сделать «видимой», для чего поверхность покрывают тонким слоем алюминия (слой B). глубина вложенности каталогов - до 8, расширения в именах каталогов запрещены 82 Глава 2. Каналы связи и т.д.). Кодиры Рида-Соломона являются ключевым компонентом компакт-диска. Это было первым использованием мложного помехоустойчивого кодирования в массовом производстве бытовой электроники. В компакт-диске двух уровневая схема кодирования дает схему, называемую кросс-чередованием Рида-Соломона кодирования (Cross- Interleaved Reed Solomon Coding-CIRC). Первый элемент декодера CIRC является RS [32,28], как сокращенный от [255,223] c 8-битными символами. Второй уровень 28-байтное блочное чередование. Т.о. используется кодо Рида-Соломона RS(255,223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами четности. Для этого кода: n = 255, k = 223, s = 8 2t = 32, t = 16 Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть, ошибки могут быть исправлены, если число искаженных байт не превышает 16. При размере символа s, максимальная длина кодового слова (n) для кода Рида- Соломона равна n = 2s – 1. Например, максимальная длина кода с 8-битными символами (s=8) равна 255 байтам. Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некоторого числа информационных символов на входе кодировщика (передавать их в этом случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив. Например, код (255,223), описанный выше, может быть укорочен до (200,168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255,223) и передаст только 168 информационных байт и 32 байта четности. Объем вычислительной мощности, необходимой для кодирования и декодирования кодов Рида-Соломона зависит от числа символов четности. Большое значение t означает, что большее число ошибок может быть исправлено, но это потребует большей вычислительной мощности по сравнению с вариантом при меньшем t. Ошибки в символах Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты не верны. Пример: Код RS(255,223) может исправить до 16 ошибок в символах. В худшем случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем случае, корректируются 16 полностью неверных байт, при этом исправляется 16 x 8=128 битовых ошибок. Коды Рида-Соломона особенно хорошо подходят для корректировки кластеров ошибок (когда неверными оказываются большие группы бит кодового слова, следующие подряд). Глава 3 Теория помехоустойчивого кодирования При передаче сообщений по цифровым каналам она кодируется. Для простоты мы будем в дальнейшем пользоваться таблицей ASCII 1 ставящей в соответствие каждой букве алфавита определенный шестнадцатеричный номер. Мы далее будем пользоваться таблицей кодов ASCII (32-255) без управляющих символов: 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 _ ! ” # $ % & ‘ ( ) ∗ + 0 − / 3 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 4 @ A B C D E F G H I J K L M N O 5 P Q R S T U V W X Y Z [ \ ] ∧ _ 6 0 a b c d e f g h i j k l m n o 7 p q r s t u v w x y z { | } ∼ del 8 Ђ ´Г ’ ´г „ † ‡ z % Љ < Њ ´ К Ћ Џ 9 ђ ‘ ’ “ ” • – — * TM љ > њ ´к ћ џ A Ў Ў J ¤ Ґ | § Ё c Є « q - r Ї B ◦ ± I i ґ µ ¶ · ё № є » j Ѕ s ї C A Б В Г Д Е Ж З И Й К Л М Н О П D Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я E а б в г д е ж з и й к л м н о п F р с т у ф х ц ч ш щ ъ ы ь э ю я Из данной таблицы следует, что для передачи одной буквы ее необходимо заменить соответствующей 7-разрядной кодовой комбинацией. Любая 7-разрядная двоичная комбинация представляет собой какой-то знак алфавита и если в процессе передачи произойдет одна ошибка, то принятая комбинация будет принадлежать другому знаку. Например, если при передаче буквы "m" (6D h = 1101101 2 ) произошла ошибка 1 ASCII (англ. American Standard Code for Information Interchange) — американский стандартный код для обмена информацией. ASCII - это кодировка для представления десятичных цифр, латинского и национального алфавитов, знаков препинания и управляющих символов. 83 84 Глава 3. Теория помехоустойчивого кодирования во 2-м разряде (разряды считаем справа), то мы получим букву "o" (1101111 2 = 6F h ). Если возникающая ошибка просто переводит одну букву алфавита в другую, то такую ошибку обнаружить не возможно. Идея помехоустойчивого кодирования заключается в добавлении к сообщению лишних символов, помогающих заметить ошибку. Теперь множество кодовых комбинаций увеличивается и состоит из двух подмножеств: - разрешенных комбинаций и - запрещенных комбинаций. Если в результате ошибки исходная комбинация перешла в множество запрещенных, то ошибку можно обнаружить. Однако, возможно, что совокупность ошибок переведет передаваемую кодовую комбинацию в другую разрешенную. Тогда вместо одной буквы мы получим другую букву и ошибка не будет обнаружена. Для того чтобы обнаруживать и исправлять ошибки, разрешенная комбинация должна как можно больше отличаться от запрещенной. Расстоянием между двумя комбинациями называется количество разрядов, которыми они отличаются. Например расстояние между буквами "m" (1101101) и "o" (1101111) будет 1. Расстояние между "a" (1100001) и "z" (1111010) будет 4. Весом комбинации называется количество в ней единиц. Очевидно что вес - это расстояние от нулевой комбинации (00000). Поскольку сумма комбинаций есть другая комбинация, то по аналогии с векторной алгеброй можно вычислять расстояние между комбинациями как вес их суммы (по модулю 2: ⊕). ⊕ 0101101 1001010 1100111 расстояние равно 5. d =5 t=2 t=2 0 Здесь d 0 - расстояние между разрешенными комбинациями, t область исправляемых ошибок. 85 000 100 010 001 111 110 101 011 t=1 t=1 t=1 t=1 d=3 t=1 t=1 t=1 Например, если расстояние между кодовыми комбинациями (000) и (111) равно d = 3, то любые единичные ошибки в этих комбинациях остаются в области t ≤ 1. Т.е. области не пересекаются и ошибки могут быть исправлены. Обозначая число (кратность) исправляемых ошибок через t i , а расстояние между разрешенными (передаваемыми) комбинациями через d 0 , заметим, что код исправит ошибки, если d 0 ≥ 2t i + 1. Для построения помехоустойчивого кода требуется к k - информационным разрядам добавить r - проверочных. Количество проверочных разрядов, необходимых для построения кода, исправляющего одну ошибку вычисляется по формуле: 2 r ≥ k + r + 1. Общее количество разрядов будет n = k+r, поэтому построенный с такими параматрами код называют [n, k] кодом. Например, для передачи 4-разрядной комбинации требуется дополнительно 3 проверочных символа и код [7, 4]. Для передачи 6-разрядной комбинации необходим [10, 6] код с 4 проверочными разрядами. Экономичность и эффективность кодов с обнаружением ошибок определяют коэффициент избыточности R u и коэффициент обнаружения K 0 : R u = 1 − lbM 1 lbM , K 0 = Q Q + Q 1 , где M = 2 n – общее число кодовых слов, которое можно получить в n-элементном коде; M 1 – количество используемых комбинаций; Q – общее количество искаженных комбинаций, ошибка в которых может быть обнаружена; Q 1 – общее число искаженных комбинаций, ошибка в которых не поддается обнаружению. 86 Глава 3. Теория помехоустойчивого кодирования 3.1 Коды Хэмминга Рассмотрим правила построения [7, 4] кода Хэмминга, исправляющего одну ошибку в передаваемой информационной комбинации (a 1 , a 2 , a 3 , a 4 ). Выпишем таблицу истинности для трех проверочных разрядов. Обозначим информационные разряды символом a i , а проверочные символом b i . Тогда, проверочные разряды восстанавливаются по информационным по следующим правилам: x 2 x 1 x 0 0 0 0 0 0 1 b 0 b 0 = a 1 ⊕ a 2 ⊕ a 4 0 1 0 b 1 b 1 = a 1 ⊕ a 3 ⊕ a 4 0 1 1 a 1 1 0 0 b 2 b 2 = a 2 ⊕ a 3 ⊕ a 4 1 0 1 a 2 1 1 0 a 3 1 1 1 a 4 Т.е. значение b 0 формируется из всех a k для которых x 0 = 1. Значение b 1 формируется из всех a k для которых x 1 = 1, и т.д. На передатчик канала связи подается самокорректирующийся код Хэмминга [7, 4], который имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 ). На приемном конце канала связи для проверочных символов строится аналогичная комбинация: B 0 = a 1 ⊕ a 2 ⊕ a 4 B 1 = a 1 ⊕ a 3 ⊕ a 4 B 2 = a 2 ⊕ a 3 ⊕ a 4 Разница между передаваемыми b i и принимаемыми B i проверочными разрядами позволяет обнаружить и локализовать ошибку. Место ошибки определяется формулой M = 2 0 · (b 0 ⊕ B 0 ) + 2 1 · (b 1 ⊕ B 1 ) + 2 2 · (b 2 ⊕ B 2 ). Пример 3.1. Построить по методу Хэмминга кодовое слово для сообщения (1010). Решение. Зная количество информационных символов k = 4 сообщения, найдем количество проверочных символов из формулы 2 r ≥ k + r + 1, или 2 3 = 8 ≥ 4 + 3 + 1 = 8, т.е. n = k + r = 4 + 3 = 7. Поскольку r = 3, то для передаваемой последовательности кода [n, k] = [7, 4] будем иметь (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 ). Учитывая, что (a 1 , a 2 , a 3 , a 4 ) = (1010), 3.1. Коды Хэмминга 87 для проверочных символов получим b 0 = a 1 ⊕ a 2 ⊕ a 4 = 1 ⊕ 0 ⊕ 0 = 1 b 1 = a 1 ⊕ a 3 ⊕ a 4 = 1 ⊕ 1 ⊕ 0 = 0 b 2 = a 2 ⊕ a 3 ⊕ a 4 = 0 ⊕ 1 ⊕ 0 = 1 Передаваемое кодовое слово имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 ) = (1011010). N Пример 3.2. На приемнике было получено кодовое слово (1101101) построенное по методу Хэмминга. Восстановить исходное сообщение. Решение. Полученное кодовое слово имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 ) = (1101101). Учитывая, что здесь a 1 = 0, a 2 = 1, a 3 = 0, a 4 = 1, для проверочных символов получим B 0 = a 1 ⊕ a 2 ⊕ a 4 = 0 ⊕ 1 ⊕ 1 = 0 B 1 = a 1 ⊕ a 3 ⊕ a 4 = 0 ⊕ 0 ⊕ 1 = 1 B 2 = a 2 ⊕ a 3 ⊕ a 4 = 1 ⊕ 0 ⊕ 1 = 0 Разница между передаваемыми b i и принимаемыми B i проверочными разрядами дает место ошибки определяемой формулой M = 2 0 · (b 0 ⊕ B 0 ) + 2 1 · (b 1 ⊕ B 1 ) + 2 2 · (b 2 ⊕ B 2 ) = 2 0 · (1 ⊕ 0) + 2 1 · (1 ⊕ 1) + 2 2 · (1 ⊕ 0) = 2 0 · 1 + 2 1 · 0 + 2 2 · 1 = 5. Отсчитывая слева направо 5-й разряд в комбинации (1101101) и меняя его на противоположный, получим (1101 101) → (1101001). Теперь выделяя информационные символы, восстановим сообщение a 1 = 0, a 2 = 0, a 3 = 0, a 4 = 1, или (0001). N 88 Глава 3. Теория помехоустойчивого кодирования Пример 3.3. Построить по методу Хэмминга кодовое слово для сообщения (111001111). Решение. Для кодирования k = 9 информационных разрядов методом Хэмминга требуется из неравенства 2 r ≥ k + r + 1. определить количество проверочных символов r. Простым подбором находим r = 4: 2 4 ≥ 9 + 4 + 1. Т.е. нам необходим код [13, 9]. Рассмотрим правила построения [13, 9] кода Хэмминга, исправляющего одну ошибку в передаваемой информационной комбинации (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 ). Выпишем таблицу истинности для четырех проверочных разрядов. Обозначим информационные разряды символом a i , а проверочные символом b i . Тогда, проверочные разряды восстанавливаются по информационным по следующим правилам: x 3 x 2 x 1 x 0 0 0 0 0 0 0 0 1 b 0 b 0 = a 1 ⊕ a 2 ⊕ a 4 ⊕ a 5 ⊕ a 7 ⊕ a 9 0 0 1 0 b 1 b 1 = a 1 ⊕ a 3 ⊕ a 4 ⊕ a 6 ⊕ a 7 0 0 1 1 a 1 0 1 0 0 b 2 b 2 = a 2 ⊕ a 3 ⊕ a 4 ⊕ a 8 ⊕ a 9 0 1 0 1 a 2 0 1 1 0 a 3 0 1 1 1 a 4 1 0 0 0 b 3 b 3 = a 5 ⊕ a 6 ⊕ a 7 ⊕ a 8 ⊕ a 9 1 0 0 1 a 5 1 0 1 0 a 6 1 0 1 1 a 7 1 1 0 0 a 8 1 1 0 1 a 9 Т.е. значение b 0 формируется из всех a k для которых x 0 = 1. Значение b 1 формируется из всех a k для которых x 1 = 1, и т.д. Учитывая, что для комбинации (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 ) = (111001111), для проверочных символов получим b 0 = a 1 ⊕ a 2 ⊕ a 4 ⊕ a 5 ⊕ a 7 ⊕ a 9 = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0 b 1 = a 1 ⊕ a 3 ⊕ a 4 ⊕ a 6 ⊕ a 7 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 0 b 2 = a 2 ⊕ a 3 ⊕ a 4 ⊕ a 8 ⊕ a 9 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 0 b 3 = a 5 ⊕ a 6 ⊕ a 7 ⊕ a 8 ⊕ a 9 = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 3.1. Коды Хэмминга 89 Кодовое слово имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 , b 3 , a 5 , a 6 , a 7 , a 8 , a 9 ) = (0010110001111). N Пример 3.4. На приемнике было получено кодовое слово (11011100101) построенное по методу Хэмминга. Восстановить исходное сообщение. Решение. Учитывая, что длина последовательности n = k+r = 11, иИз выражения 2 r ≥ k + r + 1 = n + 1 = 11 + 1 = 12 найдем количество проверочных символов r = 4. Тогда полученное кодовое слово имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 , b 3 , a 5 , a 6 , a 7 ) = (11011100101). Выпишем таблицу истинности для четырех проверочных разрядов. Обозначим информационные разряды символом a i , а проверочные символом b i . Тогда, проверочные разряды восстанавливаются по информационным по следующим правилам: x 3 x 2 x 1 x 0 0 0 0 0 0 0 0 1 b 0 b 0 = a 1 ⊕ a 2 ⊕ a 4 ⊕ a 5 ⊕ a 7 0 0 1 0 b 1 b 1 = a 1 ⊕ a 3 ⊕ a 4 ⊕ a 6 ⊕ a 7 0 0 1 1 a 1 0 1 0 0 b 2 b 2 = a 2 ⊕ a 3 ⊕ a 4 0 1 0 1 a 2 0 1 1 0 a 3 0 1 1 1 a 4 1 0 0 0 b 3 b 3 = a 5 ⊕ a 6 ⊕ a 7 1 0 0 1 a 5 1 0 1 0 a 6 1 0 1 1 a 7 Как и ранее значение b 0 формируется из всех a k для которых x 0 = 1. Значение b 1 формируется из всех a k для которых x 1 = 1, и т.д. Учитывая, что здесь (b 0 , b 1 , b 2 , b 3 ) = (1110), (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ) = (0110101), для проверочных символов получим B 0 = a 1 ⊕ a 2 ⊕ a 4 ⊕ a 5 ⊕ a 7 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1 B 1 = a 1 ⊕ a 3 ⊕ a 4 ⊕ a 6 ⊕ a 7 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0 B 2 = a 2 ⊕ a 3 ⊕ a 4 = 1 ⊕ 1 ⊕ 0 = 0 B 3 = a 5 ⊕ a 6 ⊕ a 7 = 1 ⊕ 0 ⊕ 1 = 0 90 Глава 3. Теория помехоустойчивого кодирования Разница между передаваемыми b i = (1110) и принимаемыми B i = (1000) проверочными разрядами дает место ошибки определяемой формулой M = 2 0 · (b 0 ⊕ B 0 ) + 2 1 · (b 1 ⊕ B 1 ) + 2 2 · (b 2 ⊕ B 2 ) + 2 3 · (b 3 ⊕ B 3 ) = 2 0 · (1 ⊕ 1) + 2 1 · (1 ⊕ 0) + 2 2 · (1 ⊕ 0) + 2 3 · (0 ⊕ 0) = 2 0 · 0 + 2 1 · 1 + 2 2 · 1 + 2 3 · 0 = 6. Отсчитывая слева направо 6-й разряд в комбинации (11011100101) и меняя его на противоположный, получим (11011100101) → (11011000101). Теперь выделяя информационные символы, восстановим сообщение (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ) = (0101110). N Пример 3.5. На приемнике было получено кодовое слово (001011110111111) построенное по методу Хэмминга. Восстановить исходное сообщение. Решение. Полученное кодовое слово [15, 11] имеет вид (b 0 , b 1 , a 1 , b 2 , a 2 , a 3 , a 4 , b 3 , a 5 , a 6 , a 7 , a 8 , a 9 , a 10 , a 11 ) = (001011110111111). Учитывая, что здесь (b 0 , b 1 , b 2 , b 3 ) = (0001), (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 , a 10 , a 11 ) = (11110111111), для проверочных символов получим B 0 = a 1 ⊕ a 2 ⊕ a 4 ⊕ a 5 ⊕ a 7 ⊕ a 9 ⊕ a 11 = 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0 B 1 = a 1 ⊕ a 3 ⊕ a 4 ⊕ a 6 ⊕ a 7 ⊕ a 10 ⊕ a 11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1 B 2 = a 2 ⊕ a 3 ⊕ a 4 ⊕ a 8 ⊕ a 9 ⊕ a 10 ⊕ a 11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1 B 3 = a 5 ⊕ a 6 ⊕ a 7 ⊕ a 8 ⊕ a 9 ⊕ a 10 ⊕ a 11 = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 Разница между передаваемыми b i = (0001) и принимаемыми B i = (0110) проверочными разрядами дает место ошибки определяемой формулой M = 2 0 · (b 0 ⊕ B 0 ) + 2 1 · (b 1 ⊕ B 1 ) + 2 2 · (b 2 ⊕ B 2 ) + 2 3 · (b 3 ⊕ B 3 ) = 2 0 · (0 ⊕ 0) + 2 1 · (0 ⊕ 1) + 2 2 · (0 ⊕ 1) + 2 3 · (1 ⊕ 0) = 2 0 · 0 + 2 1 · 1 + 2 2 · 1 + 2 3 · 1 = 14. Отсчитывая слева направо 14-й разряд в комбинации (001011110111111) и меняя его на противоположный, получим ((001011110111111) → (001011110111101). Теперь выделяя информационные символы, восстановим сообщение (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 , a 10 , a 11 ) = (11110111101). N 3.1. Коды Хэмминга 91 Задача 3.1. Методом Хемминга закодировать информационную последовательность. N x N x N x 1 111001 11 11111101 21 1011010011 2 101101 12 11111011 22 1101001111 3 101111 13 11110111 23 1000111111 4 110111 14 11101111 24 1111011001 5 111011 15 11011111 25 1111101101 6 111101 16 10111111 26 1110010111 7 111110 17 10011111 27 1001111011 8 100111 18 11001111 28 1111100101 9 110011 19 11100111 29 1110011110 10 111001 20 11110011 30 1001111111 Задача 3.2. На приемнике было получено кодовое слово x сформированное кодом Хемминга. Восстановить исходное сообщение. N x N x N x 1 1110001 11 0101001 21 1001001 2 0111010 12 1101010 22 0001010 3 1010011 13 0100011 23 1100011 4 1011100 14 0001100 24 1101100 5 0100001 15 1101110 25 0011111 6 0100111 16 1110110 26 0100111 7 0100100 17 1000110 27 0001011 8 1100111 18 0100110 28 0001101 9 1100100 19 1001111 29 0001110 10 1100010 20 0101111 30 1110010 92 Глава 3. Теория помехоустойчивого кодирования Задача 3.3. На приемнике было получено кодовое слово x сформированное кодом Хемминга. Восстановить исходное сообщение. N x N x N x 1 1110011100 11 001001001111 21 00100101101001 2 1011010100 12 111001001111 22 11100101101001 3 1011111010 13 100001001111 23 10000101101001 4 1101110101 14 101101001111 24 10110101101001 5 1110010011 15 101011001111 25 10101101101001 6 1110100011 16 111000011011 26 10000001011001 7 1110111011 17 111001111011 27 10000111011001 8 1110110111 18 111001001011 28 10000100011001 9 1110110001 19 111001010011 29 10000101111001 10 1110110010 20 111001011111 30 10000101001001 Задача 3.4. На приемнике было получено кодовое слово x сформированное кодом Хемминга. Восстановить исходное сообщение. N x N x 1 00101010111110111011 16 10001000111110101111011 2 11101010111110111011 17 10001000111110110111011 3 10001010111110111011 18 10001000111110111011011 4 10111010111110111011 19 10001000111110111111111 5 10100010111110111011 20 10001000111110110111011 6 101011001111101111111 21 0000111111111010111101101 7 101010101111101111111 22 1100111111111010111101101 8 101010011111101111111 23 1010111111111010111101101 9 101010000111101111111 24 1001111111111010111101101 10 101010001011101111111 25 1000011111111010111101101 11 1000100011011011111101 26 1000101111111010111101101 12 1000100011101011111101 27 1000110111111010111101101 13 1000100011110011111101 28 1000111011111010111101101 14 1000100011111111111101 29 1000111101111010111101101 15 1000100011111001111101 30 1000111110111010111101101 3.2. Циклические коды 93 3.2 Циклические коды Одним из обобщений кода Хэмминга являются циклические коды (CRC - cyclic redundancy check) 2 . В даном коде произвольная кодовая последовательность a = (a 1 , a 2 , a 3 , ..., a n ) записывается в виде полинома u(x) = a 1 x n−1 + a 2 x n−2 + ... + a n−2 x 2 + a n−1 x + a n = k X i=1 a i x k−1 Например кодовой последовательности (10101) соответствует u(x) = 1 · x 4 + 0 · x 3 + 1 · x 2 + 0 · x 1 + 1 · x 0 = x 4 + x 2 + 1, (1011) соответствует u(x) = 1 · x 3 + 0 · x 2 + 1 · x 1 + 1 · x 0 = x 3 + x 1 + 1. В поле Галуа GF (2) (Galous Field) коэффициенты при степенях x могут принимать значения только 0 или 1, тогда 1 − x − x 2 = 1 + x + x 2 , 5 + 2x + 3x 2 = 1 + 0x + x 2 = 1 + x 2 Неприводимым называется многочлен, который не может быть представлен как произведение многочленов меньшей степени. Приводимым называется многочлен, который может быть факторизован, т.е. представлен как произведение многочленов меньшей степени. Например x 3 + x = x(1 + x)(1 + x), x 4 + x = x(1 + x)(1 + x + x 2 ). Произвольный двучлен x n + 1 делится без остатка на неприводимый многочлен: x 2 + 1 = (1 + x) 2 , x 3 + 1 = (1 + x)(1 + x + x 2 ), x 4 + 1 = (1 + x) 4 , x 5 + 1 = (1 + x)(1 + x + x 2 + x 3 + x 4 ), x 6 + 1 = (1 + x) 2 (1 + x + x 2 ) 2 2 БЧХ (Bose-Chadhuri-Hocquenghem) коды являются классом циклических кодов 94 Глава 3. Теория помехоустойчивого кодирования Обозначим остаток R(x) от деления полинома P (x) на полином Q(x) через h P (x) Q(x) i , тогда P (x) Q(x) = C(x) + R(x) Q(x) т.е. P (x) Q(x) = R(x). Двоичную последовательность, соответствующую полиному остатков запишем в десятичном виде. Например x 2 x 3 + x 2 + 1 = x 2 = 100 = 4, x 3 x 3 + x + 1 = x + 1 = 011 = 3. Рассмотрим остатки от деления степени x n на неприводимый полином p(x) = x 4 + x 3 + x 2 + x + 1: x n x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 h x n p(x) i 1 2 4 8 15 1 2 4 Видно, что период последовательности составленной из остатков равен 5. Теперь рассмотрим остатки от деления степени x n на неприводимый полином p(x) = x 4 + x + 1: n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 h x n p(x) i 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 1 2 Период последовательности составленной из остатков равен 15. Неприводимый полином p(x) степени n, генерирующий последовательность остатков максимального периода T = 2 n − 1 называется примитивным или образующим. Полученный период будем называть порядком полинома ord p(x) = T. Как видно из примеров не все неприводимые полиномы могут быть примитивными. Например, для неприводимых полиномов небольших степеней n можно получить: n = 1. x x + 1 − не примитивный ord = 1 ord = 0 n = 2. x 2 + x + 1 ord = 3 n = 3. x 3 + x + 1 x 3 + x 2 + 1 ord = 7 ord = 7 n = 4. x 4 + x + 1 x 4 + x 3 + 1 x 4 + x 3 + x 2 + x + 1 − не примитивный ord = 15 ord = 15 ord = 5 В общем случае задача о нахождении всех неприводимых полиномов степени n решается с помощью формулы Мебиуса. 3.2. Циклические коды 95 Функция Мебиуса Функция Мебиуса µ k определяется следующим образом: µ k = 1, если k=1 ( −) s , если k - произведение s различных простых чисел 0 если k делится на квадрат F µ 1 = 1 F µ 2 = ( −) 1 = −1 F µ 3 = ( −) 1 = −1 F µ 4 = µ 2 2 = 0 F µ 5 = ( −) 1 = −1 F µ 6 = µ 2·3 = ( −) 2 = 1 F µ 7 = ( −) 1 = −1 F µ 8 = µ 2 2 ·2 = 0 Формула Мебиуса Количество неприводимых полиномов степени n определяется с помощью выражения I n = 1 n n X k=1,(k|n) µ k 2 n/k Здесь k|n означает что k должно делиться на n. F n = 1 : I 1 = 1 1 1 X k=1,(k|1) µ k 2 1/k = µ 1 2 1 = 2 F n = 2 : I 2 = 1 2 2 X k=1,(k|2) µ k 2 2/k = 1 2 (µ 1 2 2 + µ 2 2 1 ) = 1 2 (4 − 2) = 2 F n = 3 : I 3 = 1 3 3 X k=1,(k|3) µ k 2 3/k = 1 3 (µ 1 2 3/1 + µ 3 2 3/3 ) = 1 3 (8 − 2) = 2 F n = 4 : I 4 = 1 4 4 X k=1,(k|4) µ k 2 4/k = 1 4 (µ 1 2 4/1 + µ 2 2 4/2 ) = 1 4 (16 − 4) = 3 F n = 5 : I 5 = 1 5 5 X k=1,(k|5) µ k 2 5/k = 1 5 (µ 1 2 5/1 + µ 5 2 5/5 ) = 1 5 (32 − 2) = 6 F n = 6 : I 6 = 1 6 6 X k=1,(k|6) µ k 2 6/k = 1 6 (µ 1 2 6/1 + µ 2 2 6/2 + µ 3 2 6/3 + µ 6 2 6/6 ) = 1 6 (64 − 8 − 4 + 2) = 9 96 Глава 3. Теория помехоустойчивого кодирования 3.2.1 Исправление 1 ошибки Для того чтобы код смог исправить одну ошибку расстояние между словами должно быть не менее 3. (т.е. d = 3). Тогда количество проверочных символов r вычисляется по формуле 2 r ≥ k + r + 1 = 4 + r + 1 = 5 + r ⇒ r = 3 Для поля Галуа GF 2 таблица образующих полиномов имеет вид r P (x) 2 x 2 + x + 1 111 3 x 3 + x + 1 x 3 + x 2 + 1 1011 1101 4 x 4 + x + 1 x 4 + x 3 + 1 10011 11001 5 x 5 + x 2 + 1 x 5 + x 4 + x 3 + x 2 + 1 x 5 + x 4 + x 2 + x + 1 100101 111101 110111 6 x 6 + x + 1 x 6 + x 5 + x 2 + x + 1 1000011 1100111 7 x 7 + x 3 + 1 x 7 + x 3 + x 2 + x + 1 x 7 + x 4 + x 3 + x + 1 10001001 10001111 10011101 8 x 8 + x 7 + x 6 + x 5 + x 2 + x + 1 x 8 + x 4 + x 3 + x 2 + 1 x 8 + x 6 + x 5 + x + 1 111100111 100011101 101100011 9 x 9 + x 5 + x 3 + x 2 + 1 x 9 + x 8 + x 7 + x 6 + x 5 + x 3 + 1 1000101101 1111101001 10 x 10 + x 4 + x 3 + x + 1 x 10 + x 9 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 10000011011 11001111111 11 x 11 + x 10 + x 9 + x 8 + x 3 + x + 1 x 11 + x 8 + x 6 + x 2 + 1 111100001011 100101000101 12 x 12 + x 11 + x 9 + x 8 + x 7 + x 5 + x 2 + x + 1 x 12 + x 9 + x 3 + x 2 + 1 1101110100111 1001000001101 Если информационную последовательность представить в виде полинома m(x), то передаваемая комбинация F имеет вид F = P C, где полином C необходимо найти из выражения x r m P = C + R P Если в передаваемой комбинации возникает ошибка, то ее обнаруживают сравнением остатков от деления F P и x k P 3.2. Циклические коды 97 Пример 3.6. Рассмотрим построение повторного кода [n, k] = [3, 1]. Представим информационную последовательность в виде m(x) = e, где e ∈ GF 2 ; (e = 0, 1). Образующий полином имеет вид P (x) = x 2 + x + 1. Поскольку r = 2, то умножим x 2 m(x) = ex 2 и найдем x 2 Q(x) = C(x) · P (x) + R(x) = e · (x 2 + x + 1) + ex + e. Передаваемая последовательность имеет вид F = C(x) · P (x) = ex 2 + ex + e = (eee). Для кода малой размерности определение места ошибки проводится с помощью таблицы синдромов 3 . Обозначая через h A(x) B(x) i остаток от деления полиномов, получим 1 P (x) = 1 = (01); x P (x) = x = (10); x 2 P (x) = x + 1 = (11). Допустим мы приняли сообщение с ошибкой: I(x) = ex 2 + ex + e = (eee), тогда I(x) P (x) = x = (10) и по таблице синдромов мы определяем, что ошибка произошла во втором символе. Пример 3.7. Построить полиномиальный код [n, k] = [7, 4] для передачи информационной последовательности 0111 Решение. Для построения полиномиального кода [n, k] = [7, 4] нам необходимо иметь дополнительно r = 3 проверочных символа. Информационная последовательность a = (0111) представляется в виде m(x) = x 3 · 0 + x 2 · 1 + x · 1 + 1 · 1 = x 2 + x + 1. Поскольку r = 3, то умножаем Q(x) = x r m = x 3 Q = x 3 (x 2 + x + 1) = x 5 + x 4 + x 3 = 0111000. 3 Синдром - совокупность признаков характеризующих заболевание. Медицинский термин используемый в теории информации при построении корректирующих кодов. В данном случае синдром - это совокупность признаков характеризующих ошибку в передаваемой кодовой комбинации. 98 Глава 3. Теория помехоустойчивого кодирования По таблице образующих полиномов для r = 3 находим P (x) = x 3 + x + 1 Делим m = x r Q на образующий полином P x 3 m P = C + R P или x 5 + x 4 + x 3 x 3 + x + 1 = (x 2 + x) − 2x 2 + x x 3 + x + 1 окуда получим R = 2x 2 + x. Аналогичный результат можно получить в Mathcad: остаток от деления полиномов определяется оператором parfrac в панели Symbolic: x 5 + x 4 + x 3 x 3 + x + 1 convert, parfrac, x → x + x 2 − x · 2x + 1 x 3 + x + 1 В любом случае остаток R(x) = −(2x 2 + x) необходимо привести по модулю 2. Поскольку в этом случае 2 = 1 ⊕1 = 0 и −1 = +1, получим R(x) = −(2x 2 + x) = (2x 2 + x) = 0 · x 2 + x = x = 010. Поскольку Q(x) = x 5 + x 4 + x 3 = 0111000 то передаваемая комбинация F есть прямая конкатенация m ⊕ R, или: Q = 0111000 R = 010 F = 0111010 Таким образом, передаваемая кодовая комбинация имеет вид F = (0111010). N Допустим во время передачи по каналу информации в F возникла ошибка (3 символ слева или 4 степень) F = (01 11010) → F = (01 01010) Опишем алгоритм определения и исправления ошибки полиномиальным кодом. 3.2. Циклические коды 99 Пример 3.8. Обнаружить и исправить ошибку в последовательности F = (0101010), сформированной полиномиальным кодом. Решение. Поскольку n = 7, то по формуле 2 r ≥ n + 1 получим r = 3. Т.е. мы должны пользоваться полиномом 3 степени из таблицы полиномов. Заметим, что полином для раскодирования однозначно определяется полиномом кодирования. В кодах CRC эти полиномы совпадают. Если мы попутаем полиномы - то получим неправильный ответ. Если для данной степени неприводимых полиномов несколько, то мы будем брать первый по списку. В нашем случае для r = 3 имеем P = x 3 + x + 1. Найдем остаток от деления F P R(x) = F P = x − x 2 = x + x 2 = 0110 Составим таблицу синдромов, определяющих место ошибки в передаваемом сообщении. Найдем остаток от деления x k P : 1 P = 1 = 0001; h x P i = x = 0010 x 2 P = x 2 = 0100; x 3 P = x + 1 = 0011 x 4 P = x 2 + x = 0110; x 5 P = x 2 + x + 1 = 0111 x 6 P = x 2 + 1 = 0101; x 7 P = 1 = 0001 Заметим, что далее остатки повторяются. Место ошибки определяется степенью знаменателя синдрома, совпадающего с остатком [ F P ]. В данном случае остаток 0110 соответствует синдрому с x 4 , поэтому необходимо исправить ошибку в 4 степени передаваемой последовательности 0101010 ⇒ 0111010. Убирая последние три проверочных символа, получаем исходную информационную последовательность a = 0111. Заметим, что на практике удобнее не строить всю таблицу синдромов, а увеличивать степень числителя x k до тех пор, пока остаток h x k P i не сравняется с R(x). N 100 Глава 3. Теория помехоустойчивого кодирования В следующих задачах образующие полиномы брались первыми в списке. Задача 3.5. Построить полиномиальный код для следующей информационной последовательности. N x N x N x 1 110010011 11 10011010111 21 00110001110 2 111001 12 010100111111 22 11111001001 3 1011101 13 1101111010 23 0001011110 4 1100001011 14 01011010111 24 1110110100010 5 10100111 15 11000011 25 110001101011 6 10111010 16 100011 26 11011001010101 7 10001101 17 11010 27 11111010101011 8 100111111 18 111011010 28 1110101010111 9 1001000101 19 100011110 29 101010101011 10 1100100111 20 01000110 30 00011010110101001 Задача 3.6. На приемнике было получено кодовое слово x сформированное полиномиальным кодом. Восстановить исходное сообщение. N x N x N x N x N x 1 1100110 7 0011111 13 1010011 19 0110011 25 1101011 2 1101000 8 0110001 14 1111111 20 1001010 26 0011011 3 1000100 9 0000110 15 0111101 21 1111010 27 1001111 4 0110011 10 1001110 16 0110110 22 0100101 28 1010011 5 0010101 11 1101110 17 1011100 23 0100010 29 0110110 6 0100100 12 1110101 18 1011110 24 1001000 30 0110011 Задача 3.7. На приемнике было получено кодовое слово x сформированное полиномиальным кодом. Восстановить исходное сообщение. N x N x N x N x N x 1 001001001 7 001101111 13 101110111 19 101011111 25 001011011 2 011011111 8 111001001 14 111101111 20 101011111 26 011110111 3 110110111 9 001111111 15 100001001 21 100101111 27 001001111 4 101001111 10 111010111 16 001011101 22 101011001 28 001011110 5 111111100 11 101111111 17 111111111 23 000011111 29 101000001 6 101011111 12 101001011 18 101100111 24 111110011 30 001011101 3.2. Циклические коды 101 Задача 3.8. На приемнике было получено кодовое слово x сформированное полиномиальным кодом. Восстановить исходное сообщение. N x N x 1 10111111111111100111 16 11001111111111101001 2 11111111111111100001 17 11000011111111101011 3 11011111111111100111 18 11111101111111100111 4 00111111111111100001 19 00000011111111101011 5 00001111111111101001 20 11101111111111100111 6 01100011111111101011 21 01011111111111100001 7 11110111111111100111 22 01101111111111101001 8 01101111111111100001 23 01010011111111101011 9 01000111111111101001 24 11111011111111100111 10 01001011111111101011 25 01110111111111100001 11 11111101111111100111 26 01001011111111101001 12 01111110111111100001 27 01000111111111101011 13 01001101111111101001 28 11111110111111100111 14 01000001111111101011 29 01111111111110100001 15 11111111101111100111 30 01001110111111101001 102 Глава 3. Теория помехоустойчивого кодирования 3.2.2 Исправление 2 ошибок Алгоритм исправления 2 ошибок ничем не отличается от предыдущего. Единственная особенность заключается в выборе неприводимых полиномов и количестве проверочных символов. Нам необходимо выбрать 2 полинома: один для исправления одиночных ошибок p 1 (x), а другой для исправления двойных ошибок p 2 (x). Данные полиномы имеют степени r 1 и r 2 соответственно, и длина кода будет n = k + r 1 + r 2 символа. Тогда, согласно формуле Хэмминга r 1 + r 2 проверочных символа должны обнаружить и исправить 2 r 1 +r 2 ≥ C 0 n + C 1 n + C 2 n = 1 + n(n + 1) 2 ошибок. Однако, порядок произведения полиномов p r (x) степени r, вычисляется по формуле ord (p r · p m ) = НОК(ord p r , ord p m ) если полиномы разного порядка (степени), и ord (p r · p r ) = 2ord (p r ) если порядок (степень) полиномов одинаковый. В таком случае формулу Хэмминга необходимо переписать в виде ord (p r 1 · p r 2 ) ≥ n(n + 1) 2 Пример 3.9. Рассмотрим правила построения кода, исправляющего 2 ошибки для 1 информационного символа. Заметим, что согласно формуле Хэмминга для этого достаточно r = 4 проверочных символа 2 4 = C 0 5 + C 1 5 + C 2 5 = 1 + 5 + 10 = 16. По существу мы имеем простейший повторный код с 4 повторениями: (a) → (aaaaa). F Для построения полиномиального кода мы возьмем два примитивных полинома 2 степени p 2 = x 2 + x + 1. Тогда ord (p r · p r ) = 2ord (p r ) или ord (p 2 · p 2 ) = 2ord (p 2 ) = 2 · 3 = 6. Но 6 значений не достаточно чтобы обработать 15 возможных комбинаций ошибок. 3.2. Циклические коды 103 F Теперь возьмем 2 полинома различной степени. Например p 2 = x 2 + x + 1 и p 3 = x 3 + x + 1, тогда ord (p r · p m ) = НОК(ord p r , ord p m ) или ord (p 2 · p 3 ) = НОК(3, 7) = 3 · 7 = 21. Поскольку мы имеем 5 проверочных разрядов, то кодовая комбинация из 6 разрядов допускает C 1 6 + C 2 6 = 6 + 15 = 21 различных единичных или двойных ошибок. Т.е. нам необходим код [6, 1]. Как видно в данном случае полиномиальный код уступает по эффективности простейшему повторному коду [5, 1]. N Пример 3.10. Рассмотрим правила построения кода, исправляющего 2 ошибки для k = 2 информационных символов. F Продолжая аналогично предыдущему примеру возьмем 2 полинома 3 степени p 3 = x 3 + x + 1 и p 3 = x 3 + x 2 + 1. Тогда ord (p r · p r ) = 2ord (p r ) или ord (p 3 · p 3 ) = 2ord (p 3 ) = 2 · 7 = 14. Это недостаточно для обработки C 1 8 + C 2 8 = 8 + 28 = 36 ошибок. F Увеличиваем степени полиномов, например p 2 = x 2 + x + 1 и p 4 = x 4 + x + 1, тогда ord (p 2 · p 4 ) = НОК(3, 15) = 3 · НОК(1, 5) = 3 · 5 = 15. Поскольку мы имеем r = 6 проверочных разрядов, то кодовая комбинация из k+r = 8 разрядов допускает C 1 8 + C 2 8 = 36 различных единичных или двойных ошибок. Опять неудача. F Увеличим степени полиномов: p 3 = x 3 + x + 1 и p 4 = x 4 + x + 1, тогда ord (p 3 · p 4 ) = НОК(7, 15) = 7 · 15 = 105. Этого достаточно для обработки C 1 9 + C 2 9 = 9 + 36 = 45 ошибок. Т.е. нам необходим код [9, 2]. N Пример 3.11. Рассмотрим правила построения кода, исправляющего 2 ошибки для k = 3 информационных символов. F Продолжая аналогично предыдущему примеру возьмем 2 полинома 3 степени p 3 = x 3 + x + 1. Тогда ord (p r · p r ) = 2ord (p r ) или ord (p 3 · p 3 ) = 2ord (p 3 ) = 2 · 7 = 14. Это недостаточно для обработки C 1 9 + C 2 9 = 9 + 36 = 45 ошибок. 104 Глава 3. Теория помехоустойчивого кодирования F Увеличим степени полиномов: p 3 = x 3 + x + 1 и p 4 = x 4 + x + 1, тогда ord (p r · p m ) = НОК(ord p r , ord p m ) или ord (p 3 · p 4 ) = НОК(7, 15) = 7 · 15 = 105. Этого достаточно для обработки C 1 10 + C 2 10 = 10 + 55 = 65 ошибок. Таким образом код, исправляющий 2 ошибки при передаче 3 информационных символов должен иметь 7 проверочных разрядов и вид [n, k] = [10, 3]. N Пример 3.12. Построим код исправляющий 2 ошибки при передече информационого сообщения a = (11). Полином информациооного сообщения имеет вид m(x) = 1 + x. Для построения кодовой последовательности возьмем неприводимые полиномы p 1 = 1 + x + x 3 и p 2 = 1 + x + x 4 . Тогда x 7 m(x) (1 + x + x 3 )(1 + x + x 4 ) = x 7 (1 + x) 1 + x 2 + x 3 + x 5 + x 7 = 1 + x + x 2 + x 4 + x 5 + x 6 , или R(x) = 1 + x + x 2 + x 4 + x 5 + x 6 = (001110111) Тогда для кодовой последовательности получим F = x 7 m(x) ⊕ R(x): ⊕ 110000000 001110111 111110111 или F = 1 + x + x 2 + x 4 + x 5 + x 6 + x 7 + x 8 Допустим в кодовой последовательности возникло 2 ошибки, после чего она приняла вид F = (101110011) = 1 + x + x 4 + x 5 + x 6 + x 8 Найдем остаток от деления F P R(x) = F P = 1 + x 3 + x 5 = 0101001 Составим таблицу синдромов, определяющих место ошибки в передаваемом сообщении. Найдем остаток от деления x k +x m P : k x k 1 + x k x + x k x 2 + x k x 3 + x k x 4 + x k x 5 + x k x 6 + x k x 7 + x k 0 0000001 1 0000010 0000011 2 0000100 0000101 0000110 3 0001000 0001001 0001010 0001100 4 0010000 0010001 0010010 0010100 0011000 5 0100000 0100001 0100010 0100100 0101000 0110000 6 1000000 1000001 1000010 1000100 1001000 1010000 1100000 7 0101101 0101100 0101111 0101001 0100101 0111101 0001101 1001101 8 1101010 1011011 1011000 1011110 1010010 1001010 1111010 0111010 1110111 3.2. Циклические коды 105 Пользуясь таблицей находим, что остаток R = 0101001 соответствует остатку x 2 +x 7 , т.е. ошибкам во 2 и 7 разряде полинома кодовой комбинации. Исправляя, получим 1 01110011 ⇒ 111110111. Убирая последние семь проверочных символа, получаем исходную информационную последовательность a = (11). N Задача 3.9. На приемнике было получено кодовое слово x сформированное полиномиальным кодом [n, k] = [9, 2] с p 1 = 1+x 2 +x 3 и p 2 = 1+x+x 4 исправляющего 2 ошибки. Восстановить исходное сообщение предварительно построив таблицу синдромов. N x N x N x 1 110001101 11 101101101 21 001000110 2 110001011 12 101011101 22 010000110 3 110000111 13 101000101 23 011100110 4 110011111 14 001001011 24 011010110 5 110101111 15 111001011 25 011001110 6 111001111 16 100001011 26 011000010 7 100001111 17 101101011 27 011000100 8 010001111 18 101011011 28 011010101 9 110001000 19 101000011 29 011001101 10 110000100 20 101001111 30 011000001 Задача 3.10. На приемнике было получено кодовое слово x сформированное полиномиальным кодом с p 1 = 1 + x + x 2 и p 2 = 1 + x 3 + x 5 исправляющего 2 ошибки. Восстановить исходное сообщение. N x N x N x 1 001010110111 11 000111001000 21 0100111111011 2 001010110100 12 000111001110 22 0100111110111 3 001010110010 13 000111000010 23 0100111101111 4 001010111110 14 000111011010 24 0100111011111 5 001010100110 15 000111101010 25 0100110111111 6 101110111110 16 001110011011 26 0011001001111 7 101000111110 17 001101011011 27 0011111001111 8 101011111110 18 001011011011 28 0010011001111 9 101010011110 19 000111011011 29 0001011001111 10 101010101110 20 011111011011 30 0111011001111 106 Глава 3. Теория помехоустойчивого кодирования 3.3 Коды Рида-Миллера Коды Рида-Маллера предложены в 1954 г. и обозначаются как RM(r, m), где r- порядок кода, 2 m -длина кода. Порождающая матрица кода RM(0, m) имеет вид строки из 2 m единиц: G 0,m = G 0 (m) = (1, 1, ..., 1). Порождающая матрица кода RM(1, 3) имеет вид G 1,3 = G 1 (3) = 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 Для кодирования информационного сообщения x длиной k = m + 1 необходимо подействовать на него оператором G справа: y = xG. Результатом кодирования будет кодовое слово y длиной n = 2 m Декодирование кода использует матрицу Адамара. Мы возмем рекурсивную формулу для построения матриц Адамара H k+1 = H k H k H k −H k где H 0 = 1. Например H 0 = 1; H 1 = H 0 H 0 H 0 −H 0 = 1 1 1 −1 ; H 2 = H 1 H 1 H 1 −H 1 = 1 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 1 ; H 3 = H 2 H 2 H 2 −H 2 = 1 1 1 1 1 1 1 1 1 −1 1 −1 1 −1 1 −1 1 1 −1 −1 1 1 −1 −1 1 −1 −1 1 1 −1 −1 1 1 1 1 1 −1 −1 −1 −1 1 −1 1 −1 −1 1 −1 1 1 1 −1 −1 −1 −1 1 1 1 −1 −1 1 −1 1 1 −1 ...и т.д. Декодирование по принципу максимального правдоподобия означает выбор из всех возможных кодовых слов того слова y, которое находится на минимальном расстоянии Хэмминга от принятого слова. 3.3. Коды Рида-Миллера 107 Процесс декодирования выводится из формул y 0 = x 0 , y 2 i = x 0 ⊕ x m−i или x 0 = y 0 , x m−i = y 0 ⊕ y 2 i , где i = 0, 1, ..., m − 1. Пример 3.13. Построим RM(1, 3)-код для информационого сообщения a = (1011). y = xG = (1011) 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 = (10011001). Перед процессом декодирования перепишем кодовое слово используя формулу Y = 2y − 1 т.е. Y = (1, −1, −1, 1, 1, −1, −1, 1) и подействунм на него матрицей Адамара H 3 справа z = YH 3 = (1, −1, −1, 1, 1, −1, −1, 1) 1 1 1 1 1 1 1 1 1 −1 1 −1 1 −1 1 −1 1 1 −1 −1 1 1 −1 −1 1 −1 −1 1 1 −1 −1 1 1 1 1 1 −1 −1 −1 −1 1 −1 1 −1 −1 1 −1 1 1 1 −1 −1 −1 −1 1 1 1 −1 −1 1 −1 1 1 −1 = (00080000). Наибольшая по модулю компонента 8 - четвертая слева. Следовательно ближайшем кодовым словом будет 4 столбец матрицы Адамара H 3 , т.е. вектор y = (1, −1, −1, 1, 1, −1, −1, 1) ∼ = (10011001). Декодирование производится по формулам x 0 = y 0 = 1 x 3 = y 0 ⊕ y 1 = 1 ⊕ 0 = 1 x 2 = y 0 ⊕ y 2 = 1 ⊕ 0 = 1 x 1 = y 0 ⊕ y 4 = 1 ⊕ 1 = 0 т.е. x = (1011). Напомним, что в последней формуле нумерация символов производится с нуля. Допустим, в передаваемом сообщении возникла ошибка (например в 5 символе слева) y = (10010001). 108 Глава 3. Теория помехоустойчивого кодирования Перед процессом декодирования перепишем кодовое слово используя формулу Y = 2y − 1 т.е. Y = (1, −1, −1, 1, −1, −1, −1, 1) и подействунм на него матрицей Адамара H 3 справа z = YH 3 = (1, −1, −1, 1, −1, −1, −1, 1).H 3 = ( −2, −2, −2, 6, 2, 2, 2, 2). Наибольшая по модулю компонента 6 - четвертая слева. Следовательно ближайшем кодовым словом будет 4 столбец матрицы Адамара H 3 . Декодируя аналогично предыдущему случаю получим ответ x = (1011). Задача 3.11. На приемнике было получено кодовое слово y сформированное кодом Рида-Маллера RM(1, 3). Восстановить исходное сообщение. N y N y N y N y N y 1 10101010 7 11000010 13 10010111 19 11011100 25 00101100 2 10101000 8 11000001 14 10010100 20 11000100 26 00110100 3 10101110 9 11000111 15 10010010 21 11001000 27 00111000 4 10100010 10 11001011 16 10011110 22 11001110 28 00111110 5 10111010 11 11010011 17 10000110 23 11111000 29 11110010 6 11100000 12 11001101 18 00111101 24 11110100 30 11110001 Задача 3.12. На приемнике было получено кодовое слово y сформированное кодом Рида-Маллера RM(1, 4). Восстановить исходное сообщение. N y N y N y 1 1001011010010111 11 1001100110011000 21 1111000000001110 2 0011001111001110 12 0011110011000001 22 0011001111001110 3 1001011010010010 13 1001100110011101 23 1111000000001011 4 1001011010011110 14 1001100110010001 24 1111000000000111 5 0011001111011100 15 0011110011010011 25 0011110011010011 6 1001011010110110 16 1001100110111001 26 1111000000101111 7 1001011011010110 17 1001100111011001 27 1111000001001111 8 0011001101001100 18 0011110001000011 28 0011001101001100 9 1001011110010110 19 1001100010011001 29 1111000100001111 10 0011000111001100 20 0011111011000011 30 0011111011000011 3.4. Сверточные коды 109 3.4 Сверточные коды Наиболее распространенным видом помехоустойчивого кодирования в настоящее время являются сверточные коды: - протоколы беспроводной связи IMT-2000, GSM, IS-95 - цифровые наземные и спутниковые системы связи - системы связи с дальним космосом. Основные принципы работы этих кодов построены на теории автоматов. 3.4.1 Блочное чередование При передаче информации ошибки как правило появляются пакетами. К примеру такой источник ошибок как грозовая молния длится от 10 до 100ms. Если мы используем CDMA на частоте 1.23MHz и скорости 153kbs, то одна вспышка молнии запросто уничтожает от 1.5 до 15kb передаваемых данных. Если вы передаете SMS по сотовому телефону GSM на скорости 9.6 kbs, то можете потерять до 960bt. Поскольку в кодировке UTF16 каждая русская буква занимает 2Bt=16bt, то 960bt - это сообщение из 60 символов. Для защиты от пакетных ошибок в GSM используется алгоритм перемежения, который позволяеь преобразовать пакет в независимые ошибки. Для этого кодовая комбинация (a 1 a 2 a 3 ...a n ) длиной n записывается построчно в матрицу размером k ×k a 1 a 2 a k a k+1 a k+2 ... a 2k ... a k 2 = a 11 a 12 ... a 1k a 21 a 22 ... a 2k a k1 a k2 ... a k 2 а считывается по столбцам (a 11 a 21 a 31 ...a k 2 ). В результате исходные символы, которые следовали друг за другом, передаются в канал с интервалом в k символом, который называется глубиной перемежения. Если матрица квадратная, то процесс декодирования аналогичен предыдущему алгоритму. Если же матрица прямоугольная то декодирование производится в обратном порядке: последовательность записывается по столбцам, а считывается построчно. Например возьмем сообщение выстрел и закодируем его повторным кодом [n, k] = [3, 1]. Получим кодовую комбинацию вввыыыссстттррреееллл. Допустим во время передачи этого сообщения оно было искажено пакетной ошибкой, т.е. заменим последовательно 5 символов начиная с 8-го на букву а вввыыысаааааррреееллл. Если попытаться раскодировать это сообщение как есть, то мы получим ввв ыыы саа ааа ррр еее ллл ⇒ выаарел. Теперь перед отправлением сообщения используем метод перемежения. Для этого 110 Глава 3. Теория помехоустойчивого кодирования запишем исходную комбинацию в матрицу построчно в в в ы ы ы с с с т т т р р р е е е л л л _ _ _ и считаем по столбцам вытелвсте_всре_ы cрл_ытрл. Допустим во время передачи этого сообщения оно было искажено такой же пакетной ошибкой: вытелвсаааааре_ысрл_ытрл. Запишем принятую комбинацию в матрицу по столбцам в в а ы ы ы с а с т т а р р р е а е л л л а _ _ и прочитаем построчно вва ыыы сас тта ррр еае ллл а__ ⇒ выстрел. Как видно сообщение без труда восстанавливается в правильном виде. 3.4.2 Теория автоматов Автоматом называется система, меняющая свое состояние под действием обрабатываемого входного сигнала. В этом случае значения выходного сигнала зависят не только от входного значения, но и от текущего состояния самой системы. Для описания работы автомата необходимо задать - вектор значений входящего сигнала a = (a 1 a 2 ...a n ), - вектор внутренних состояний автомата s = (s 1 s 2 ...s n ). Во время работы на вход автомата подается очередное значение сигнала a i . В зависимости от текущего состояния s k автомат изменяет значение сигнала на z i , но и сам под воздействием входного сигнала меняет свое состояние на s m . Следующее значение сигнала a i+1 автомат принимает находясь в состоянии s m и в соответствии со своим состоянием формирует выходное значение z i+1 , а сам при этом меняет свое состояние на s n и т.д. Как видно, для описания работы автомата нам необходимо задать еще - вектор возможных значений выходного сигнала z = (z 1 z 2 ...z n ), - функцию перехода g: (a k s k ) → (z k ), которая создает значения выходного сигнала z k из входного s k с учетом текущего состояния автомата s k - функцию перехода f: (a k s k ) → (s k+1 ), которая меняет состояние автомата s k на s m в зависимости от значения принятого сигнала a k и текущего состояния автомата s k Поскольку все значения являются дискретными, то функции f и g как правило задают таблицами. 3.4. Сверточные коды 111 Пример 3.14. На вход автомата подается сигнал a = (0011101010). Получить выходной сигнал, если функции перехода f и g автомата заданы таблицей. f g 0 1 0 1 s 0 s 1 s 0 0 1 s 1 s 1 s 2 1 1 s 2 s 0 s 1 1 0 Решение. 1 метод. Исследование работы автомата удобнее проводить в два этапа. На первом этапе мы рассмотрим изменение состояния автомата под действием входного сигнала (т.е. функцию f). Запишем в строку значения входного сигнала a = (0011101010). Начальное состояние автомата s 0 запишем над первым значением. Первое значение входного сигнала a 1 = 0. По таблице для f на пересечении s 0 и 0 находим новое состояние автомата s 1 и запишем его над вторым значением сигнала: s 0 −→ s 1 0 % Второе значение входного сигнала a 2 = 0. По таблице для f на пересечении s 1 и 0 находим новое состояние автомата s 1 и запишем его над третьим значением сигнала: s 0 −→ s 1 −→ s 1 0 % 0 % Третье значение входного сигнала a 3 = 1. По таблице для f на пересечении s 1 и 1 находим новое состояние автомата s 2 и запишем его над четвертым значением сигнала: s 0 −→ s 1 −→ s 1 −→ s 2 0 % 0 % 1 % и т.д. Полная последовательность состояний, принимаемых автоматом под воздействием входного сигнала имеет вид s k s 0 → s 1 → s 1 → s 2 → s 1 → s 2 → s 0 → s 0 → s 1 → s 2 a 0 % 0 % 1 % 1 % 1 % 0 % 1 % 0 % 1 % 0 Теперь, зная все состояния автомата найдем выходной сигнал используя функцию g таблицы. Для первого значения входного сигнала a 1 = 0 и состояния s 0 найдем выходное значение 0: s 0 0 0 112 Глава 3. Теория помехоустойчивого кодирования Для второго значения входного сигнала a 2 = 0 и состояния s 1 найдем выходное значение 1: s 0 s 1 0 0 0 1 Для третьего значения входного сигнала a 3 = 1 и состояния s 1 найдем выходное значение 1: s 0 s 1 s 1 0 0 1 0 1 1 и т.д. Дальнейшую динамику работы автомата можно проследить по таблице s k s 0 → s 1 → s 1 → s 2 → s 1 → s 2 → s 0 → s 0 → s 1 → s 2 a 0 % 0 % 1 % 1 % 1 % 0 % 1 % 0 % 1 % 0 F 0 1 1 0 1 1 1 0 1 1 Таким образом, выходная последовательность работы автомата имеет вид z = (0110111011). 2 метод. Каждому автомату можно поставить в соответствие ориентированный граф, если в качестве узлов графа взять состояния автомата s k , а в качестве веса ребра - значение a k /z k Тогда граф, соответствующий предыдущей задаче имеет вид 1/1 0/0 0/1 1/0 1/1 0/1 s 0 s 1 s 2 s 0 s 0 s 1 s 1 s 2 s 2 1/1 0/0 0/1 1/1 0/1 1/0 По заданному графу мы построим базисный треллис - схему изменения состояний системы на одном шаге. Размножая данный базисный треллис до размера, равного длине входной последовательности мы построим треллис автомата. Теперь, начиная из состояния S 0 будем выделять ребра, числители которых на каждом шаге совпадают с данными входной последовательности. 3.4. Сверточные коды 113 Тогда знаменатели выделенных ребер соответствуют выходной последовательности работы автомата. s 0 s 0 s 1 s 1 s 2 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 s 0 s 1 s 2 0/0 0/1 1/1 1/0 1/1 0/1 1/1 0/0 1/1 0/1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 Как и в 1 случае, выходная последовательность работы автомата имеет вид z = (0110111011). N Пример 3.15. На вход автомата подается сигнал M. Построить граф автомата и найти выходной сигнал, если функции перехода f и g автомата заданы таблицей. f g 0 1 0 1 s 0 s 1 s 3 0 1 s 1 s 1 s 2 1 1 s 2 s 0 s 1 0 0 s 3 s 0 s 1 1 1 0/1 0/0 1/1 1/1 0/1 0/0 s 1 s 2 s 3 s 0 1/0 1/1 Решение. Граф автомата и его базисный треллис показан на рисунке. Символу M соответствует ASCII код 4d т.е. в двоичной системе исчисления на вход автомата подается сигнал z = (1001101). Выходная последовательность работы автомата имеет вид z = (1101011) или 6b что соответствует ASCII символу k. N s 0 s 0 s 1 s 1 s 2 s 2 s 3 s 3 1/1 0/0 0/1 1/1 0/0 1/0 1/1 0/1 114 Глава 3. Теория помехоустойчивого кодирования Задача 3.13. На вход автомата подается ASCII код первой буквы фамилии курсанта. Получить выходной сигнал, если функции перехода f и g автомата заданы таблицей. Начертить граф автомата. 01 f g 0 1 0 1 s 0 s 0 s 2 0 1 s 1 s 1 s 3 1 1 s 2 s 0 s 2 1 1 s 3 s 1 s 3 1 1 02 f g 0 1 0 1 s 0 s 1 s 2 0 1 s 1 s 1 s 3 0 1 s 2 s 3 s 1 1 1 s 3 s 2 s 1 1 1 03 f g 0 1 0 1 s 0 s 1 s 3 0 1 s 1 s 1 s 2 1 1 s 2 s 2 s 1 0 1 s 3 s 3 s 1 1 1 04 f g 0 1 0 1 s 0 s 1 s 2 0 1 s 1 s 1 s 2 1 1 s 2 s 1 s 2 1 1 s 3 s 1 s 2 0 1 05 f g 0 1 0 1 s 0 s 0 s 2 0 1 s 1 s 0 s 2 1 1 s 2 s 0 s 2 1 1 s 3 s 0 s 2 1 1 06 f g 0 1 0 1 s 0 s 0 s 2 0 1 s 1 s 1 s 3 1 1 s 2 s 2 s 0 1 0 s 3 s 3 s 1 1 1 07 f g 0 1 0 1 s 0 s 1 s 3 0 1 s 1 s 2 s 0 1 1 s 2 s 3 s 1 1 1 s 3 s 0 s 2 1 0 08 f g 0 1 0 1 s 0 s 1 s 2 0 1 s 1 s 2 s 3 1 0 s 2 s 3 s 0 1 1 s 3 s 0 s 1 1 1 09 f g 0 1 0 1 s 0 s 3 s 1 0 0 s 1 s 0 s 2 1 1 s 2 s 0 s 2 1 1 s 3 s 3 s 1 1 1 10 f g 0 1 0 1 s 0 s 1 s 2 0 1 s 1 s 1 s 2 0 1 s 2 s 0 s 1 1 0 s 3 s 1 s 1 1 0 11 f g 0 1 0 1 s 0 s 1 s 2 1 1 s 1 s 1 s 0 0 1 s 2 s 2 s 1 0 0 s 3 s 0 s 1 1 0 12 f g 0 1 0 1 s 0 s 1 s 0 0 1 s 1 s 1 s 2 1 1 s 2 s 0 s 2 1 0 s 3 s 0 s 2 0 0 13 f g 0 1 0 1 s 0 s 1 s 0 1 1 s 1 s 1 s 0 0 1 s 2 s 0 s 1 1 0 s 3 s 0 s 1 0 0 14 f g 0 1 0 1 s 0 s 1 s 2 1 1 s 1 s 1 s 2 1 1 s 2 s 0 s 1 0 0 s 3 s 0 s 1 0 0 15 f g 0 1 0 1 s 0 s 1 s 2 0 1 s 1 s 1 s 2 0 0 s 2 s 3 s 1 1 1 s 3 s 3 s 1 1 0 16 f g 0 1 0 1 s 0 s 1 s 3 0 1 s 1 s 2 s 3 1 0 s 2 s 3 s 1 0 1 s 3 s 0 s 1 1 0 17 f g 0 1 0 1 s 0 s 1 s 2 1 1 s 1 s 2 s 2 0 0 s 2 s 3 s 1 0 1 s 3 s 0 s 1 1 0 18 f g 0 1 0 1 s 0 s 1 s 0 0 1 s 1 s 2 s 3 1 0 s 2 s 3 s 2 1 1 s 3 s 0 s 1 0 0 19 f g 0 1 0 1 s 0 s 0 s 0 1 1 s 1 s 1 s 1 0 0 s 2 s 2 s 2 1 1 s 3 s 3 s 3 0 0 20 f g 0 1 0 1 s 0 s 0 s 3 1 1 s 1 s 3 s 1 1 0 s 2 s 2 s 2 0 1 s 3 s 1 s 0 0 0 21 f g 0 1 0 1 s 0 s 1 s 0 0 1 s 1 s 2 s 0 0 0 s 2 s 3 s 1 1 0 s 3 s 3 s 1 1 1 22 f g 0 1 0 1 s 0 s 1 s 0 0 1 s 1 s 2 s 0 1 0 s 2 s 3 s 2 0 0 s 3 s 3 s 2 1 1 23 f g 0 1 0 1 s 0 s 1 s 0 1 1 s 1 s 2 s 0 0 0 s 2 s 3 s 3 0 0 s 3 s 3 s 3 1 1 24 f g 0 1 0 1 s 0 s 0 s 0 0 1 s 1 s 1 s 3 1 0 s 2 s 2 s 0 1 0 s 3 s 3 s 3 0 1 3.4. Сверточные коды 115 25 f g 0 1 0 1 s 0 s 0 s 2 1 1 s 1 s 1 s 3 0 0 s 2 s 2 s 0 1 0 s 3 s 3 s 1 0 1 26 f g 0 1 0 1 s 0 s 0 s 1 1 1 s 1 s 1 s 2 1 0 s 2 s 2 s 3 0 0 s 3 s 3 s 0 0 1 27 f g 0 1 0 1 s 0 s 0 s 1 0 0 s 1 s 1 s 2 0 1 s 2 s 2 s 1 1 0 s 3 s 3 s 2 1 1 28 f g 0 1 0 1 s 0 s 0 s 0 0 0 s 1 s 1 s 0 1 1 s 2 s 2 s 0 0 0 s 3 s 3 s 0 1 1 3.4.3 Сверточные коды Сверточным кодом называется автомат, обрабатывающий двоичную последовательность и имеющий 4 состояния s = (s 0 , s 1 , s 2 , s 3 ): f g 0 1 0 1 s 0 s 0 s 2 00 11 s 1 s 0 s 2 11 00 s 2 s 1 s 3 10 01 s 3 s 1 s 3 01 10 Пример 3.16. Согласно таблице перехода для входной последовательности a = (1, 1, 0, 1, 1, 1, 0, 0) автомат выдаст сигнал F = (11, 01, 01, 00, 01, 10, 01, 11). N 0/00 0/11 1/11 1/00 0/10 0/01 1/01 1/10 s 0 s 2 s 1 s 3 00 00 11 11 01 01 10 10 s 0 s 0 s 1 s 1 s 2 s 2 s 3 s 3 Работу автомата удобно описывать с помощью развернутой решеточной диаграммы - треллиса a Поскольку изначально предполгается что автомат находился в состоянии s 0 , то любой путь начинается из левого верхнего угла треллиса. На каждом шаге путь вдоль диаграммы может принимать два направления. Если очередной символ информационной последовательности принимает значение 0 - автомат выбирает верхнее ребро; 1 - автомат выбирает нижнее ребро. Выходная кодовая последовательность автомата равна весу всех ребер выбранного пути. a trellis diagram - (англ.) решеточная диаграмма |