Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 73
Текст из файла (страница 73)
"Платой" за это преимущество является сужение класса всех линейных кодов до БЧХ. Кроме того, доказывается, что достаточно длинные БЧХ-коды имеют минимальное кодовое расстояние значительно худшее, чем то, которое гарантируется границей Варшамова-Гильберта. Впрочем, существуют такие классы кодов, как, например, коды Гоппы1) облцдающие как хорошим а1, так и конструктивным алгебраическим алгоритмом декодирования. 7.3.6, ОБОБЩЕНИЕ ТЕОРИИ КОДИРОВАНИЯ НА НЕДВОИЧНЫЕ КОДЫ До сих пор мы рассматривали только двоичные линейные коды. Однако это делалось лишь для простоты.
На самом деле теория линейных кодов обычно излагается сразу для тичных кодов, где т = р', р — простое число, 1 — натуральное число, т.е. для случая, когда символы кода образуют конечное поле Галуа бж(4) и над ними могут быть осуществлены все арифметические действия, которые существуют над вещественными или комплексными числами. Для таких т-ичных кодов могут быть определены все понятия и доказаны все свойства, полученные ранее для двоичных кодов, а именно — порождающая и проверочная матрицы, систематические коды, дуэльные коды, границы минимальных расстояний, стандартные расположения, синдромы, весовые спектры и границы для р и р,„, циклические и БЧХ-коды, алгебраические и мажоритарные алгоритмы декодирования.
Наиболее важным классом яичных кодов являются коды Рида-Соломона (кратко РС-коды). Они могут быть построены как систематические циклические (л, й)-коды при л = ц — 1, л — я = 21, 1 — число исправляемых ошибок. Коды РС являются частью стандарта цифровой записи на компакт-диски. ') Мак Вильямс Ф.
Дж, Слоэн Н. Дж. Теория кодов, исправляющих ошибки/ Пер. с англ.; Под ред. Л.А. Бассалыго — М.: Связь, 1979. 289 По определению вектор х является словом «п-ичного (и, к)-кода РС, если соответствующий ему многочлен Я0) имеет корни равные элементам поля бя (й): а, а', ..., а" ", где а- примитивный элемент этого поля. Порождающий многочлен кода РС имеет вид 8(0)=(0 — а)(0 — а )...(0 — а" «) . (7.78) Как видно из определения РС-кода, он является частным случаем в-нчных БЧХ-кодов, и согласно доказанному ранее, минимальное кодовое расстояние таких кодов будет в точности равно о( = и — й + 1. Легко показать, что никакой линейный систематический «и-ичный («и > 2) код не может иметь «(> и — и+ 1.
Действительно, если выбрать значения и минус одного информационного символа равными нулю, то это даст ненулевое кодовое слово веса не более чем и— к + 1, что по свойству линейного кода и определяет верхнюю границу для Ф как и — к + 1. Посколъку РС-код реализует верхнюю границу для минимального кодового расстояния, то он оказывается оптимальным среди всех в-ичных (и, я)-кодов в смысле исправления и обнаружения ошибок гарантированной кратности. Можно дать простые описания РС-кода в несистематическом представлении.
Тогда кодовый вектор определяется как ~Р(1) Р(о) Р(о«) Р~ов-«)1 (7.79) где Р(0)=Ь,+Ь,0+...«-Ь«,0 ', (Ь,, Ь,, ..., Ь«,) — значения информационных «п-ичных символов. Выбор длины кода и = д — 1 является достаточно сильным ограничением, особенно при большом порядке поля. Поэтому можно строить так называемые укороченные коды РС, имеющие произвольную длину и я д — 1. Их можно получить из полных РС кодов, имеющих длину и = и —. 1, если положить часть информационных символов равными нулю и выбросить их из кодовых блоков.
Легко видеть, что укорочение кода не может уменьшить минимального кодового расстояния, и поэтому (и, к)-код при и ~ о — 1 будет по-прежнему иметь И=и †к. Коды РС, являясь частным случаем БЧХ кодов, имеют алгебраический алгоритм исправления ошибок с полиномиальной сложностью. Коды «и могут быть использованы совместно с двоичными кодами для построения так называемых каскадных кодов. 7.3.7 ИТЕРАТИВНЫЕ И КАСКАДНЫЕ КОДЫ Ввод данных Внешннн кодер Вну нний Внешний Вывод данных Канал декодер декодер Внутренний кодер (п„к,) (п„Ь,) т>2 пг=2 Рис.7.б.
Схема каскадного кодирования и декодирования 290 Мощные коды (т.е. коды с длинными блоками И большим кодовым расстоянием 4 при сравнительно простой процедуре декодирования можно строить, объединяя несколько коротких кодов. Так строится, например, итеративный код из двух линейных систематических кодов (пп к1) и (пъ йз) — см. табл.
7.4. Вначале сообщение кодируется кодом 1-й ступени (пп к1). Пусть |сз блоков кода 1-й ступени записаны в виде строк матрицы. Ее столбцы содержат по йт символов, которые будем считать информационными для кода 2-й ступени (пз,йг) и подпишем к ним пз — йз проверочных символов. В результате получится блок (матрица п1 х п1), содержащий п|пт символов, из которых й«йз являются информационными. Процесс построения кода можно продолжить в 3-м измерении и т.д. При декодировании каждого блока 1-й ступени обнаруживают и исправляют ошибки. После того как принят весь двумерный блок, вновь исправляют ошибки и стирания, но уже по столбцам, кодом 2-й ступени, причем приходится исправлять только те ошибки, которые не были исправлены (или были ложно "исправлены") кодом 1-й ступени.
Легко убедиться, что минимальное кодовое расстояние для двумерного итеративного кода о(= 4«,п где а(1 и 'а!з— соответственно минимальные кодовые расстояния для кодов. 1-й и 2-й ступени. Весьма эффективная разновидность мощных кодов — каскадные коды. Двухкаскадный код (рис. 7.б) строится следующим образом: сначала к«двоичных символов источника Покажем, как можно найти коэффициенты многочлена локаторов ошибки «г,, ..., «г по известным координатам синдрома зо ..., х„,. 1 Положим г = — в выражении (7.74), что дает равенство хт 1 1 1 1+о,— +ег — г+...+о~ — „= О. (7.7б) хз х~ х~ Умножим (7.7б) на х,'-~ «+в !+в -1 ив -г хт + о,х + «ггхт +...+ о„хт — — О и просуммируем по всем 1= 1, 2, ..., в . Тогда получим А, +а,А, „,+о А, +...+о А, =О, А, =х,, 1=1, ..., 21 — 1. (7.77) Система уравнений (7.77) является линейной, и поэтому если ее решение существует, то оно может быть легко найдено.
Доказывается [211, что если число действительно произошедших ошибок не превосходит г, то система (7.77) имеет решение. После нахождения неизвестных оп ..., а„можно по (7.74) вычислить многочлен локаторов ошибок. Затем находятся корни этого многочлена е,, аг, ..., а и, наконец, локаторы ошибок х~ — -а~~. Очевидно, что нахождение локаторов ошибок позволяет найти положения самих ошибок е, на кодовом 9 блоке, т.е. произвести исправление ошибок. Как видно, при использовании алгебраических методов декодирования процедура исправления ошибок имеет полиномиальную сложность в зависимости от числа ошибок а, чем она существенно отличается от зкспоненциально сложной процедуры декодирования методом перебора всех образцов ошибок.
"Платой" за это преимущество является сужение класса всех линейных кодов до БЧХ. Кроме того, доказывается, что достаточно длинные БЧХ-коды имеют минимальное кодовое расстояние значительно худшее, чем то, которое гарантируется границей Варшамова-Гильберта. Впрочем, существуют такие классы кодов, как, например, коды Гоппы1) обладающие как хорошим «;(, так и конструктивным алгебраическим алгоритмом декодирования. 7.3.6. ОБОБЩЕНИЕ ТЕОРИИ КОДИРОВАНИЯ НА НЕДВОИЧНЫЕ КОДЫ До сих пор мы рассматривали только двоичные линейные коды.
Однако это делалось лишь для простоты. На самом деле теория линейных кодов обычно излагается сразу для лгичных кодов, где лг = р', р — простое число, 1 — натуральное число, т.е. для случая, когда символы кода образуют конечное поле Галуа бзт(д) и над ними могут быть осуществлены все арифметические действия, которые существуют над вещественными или комплексными числами. Для таких га-ичных кодов могут быть определены все понятия и доказаны все свойства, полученные ранее для двоичных кодов, а именно — порождающая и проверочная матрицы, систематические коды, дуальные коды, границы минимальных расстояний, стандартные расположения, синдромы, весовые спектры и границы для р и р,„, циклические и БЧХ-коды, алгебраические и мажоритарные алгоритмы декодирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
