У. Питерсон - Коды, исправляющие ошибки (1267328), страница 70
Текст из файла (страница 70)
Приведенное здесь изложение алгоритмов основано на работе Месси [21 Ц. Этапы 3 и 4 (равд. 9.4) были упрощены соответственно Цянем [49] и Форин [89]. Идеи равд. 9.7 основаны на работах [24, 89]. Негациклическне коды были построены Берлекэмпом [20]. Задачи 9Л. Покажите, что любой двоичный код, порожденный много- членом д(Х) = 8'*(Х).
имеющим 1 среди своих корней, есть БЧХ- „од с минимальным расстоянием не меньше 6. Покажите, что это утверждение применимо к любым нз двух двоичных циклических (17 8)-кодов. 9.2. Покажите, что если в определении БЧХ-кодов элемент а заменить на любой другой элемент и' того же порядка, то получится эквивалентный код. (Указание: сначала покажите, что каждый из элементов и и сс' может быть представлен как степень другого.) 9.8. Покажите, что код Рида — Соломона с символами из Сг (д), порожденный многочленом 8'(Х)=(Х вЂ” а) (Х вЂ” аа) ... (Х вЂ” аи-'), где а — примитивный корень 6Г(д), имеет минимальное расстояние И.
9.4. Пусть С~ — двоичный циклический (а,й)-код с конструктивным расстоянием 2!ь Предполагается, что порождающий многочлен а1(Х) кода С1 не делится на Х+ 1. Пусть теперь Са — циклический (л,й — 1)-код, порожденный (Х+ 1)д1(Х), н этот код имеет конструктивное расстояние 2!а ~ 2!ь Покажите, что действительное минимальное расстояние С~ равно по меньшей мере 2!1 + 1. 9.5. Используя результаты предыдущей задачи, докажите, что (17,9)- и (65,53)-коды БЧХ имеют расстояние 5. 9.6.
Используя результаты двух предыдущих задач, покажите, что все циклические (2 +1,2'"+1 — 2т)-коды имеют расстояние 5. Заметим, что эти коды несколько лучше, чем примитивные БЧХ-коды с тем же минимальным расстоянием и числом проверочных символов. 9,7. В системе передачи данных, работающей со скоростью 10090 бит/с, требуется использовать двоичный БЧХ-код длины 65 535 = 2'а — 1 или меньше со скоростью Й =- 0,75 (А = 49 151). Такой код исправляет все комбинации (приблизительно) из 1050 нли меньшего числа ошибок.
Определите скорость, с которой должны работать логические схемы. Определите также стоимость устройства, допуская, что для каждого триггера требуются 4 схемы совпадений, и предполагая, что стоимость схемы совпадений составляет 1 долл., а триггера — 2 долл. (Имеется запоминающее устройство с ограниченным временем выборки для двух принятых слов стоимостью 5000 долл.) 9.8. Большая универсальная цифровая машина, с которой вы наиболее знакомы, используется для декодирования кода нз предыдущей задачи. Подсчитайте число операций, требуемых на каждом этапе процедуры декодирования, и определите максимальную скорость поступления информации, которую может обработать машина.
(Не забывайте, что имеется только одно арифметическое устройство.) 9.9. Рассмотрите д-ичный циклический код с минимальным расстоянием г(. Канал стирает е(е ( и) символов. Декодирование осуществляется следующим образом. Декодер подставляет вместо е стертых символов какие-либо значения н пытается исправить получившиеся при этом ошибки (возможно, используя процедуру, описанную в равд. 9.4, если выбран БЧХ-код).
Декодирование заканчивается, если в результате получится истинное кодовое слово. В противном случае производится вторая попытка и снова декодер пытается исправить ошибки. Покажите, что должно быть сделано по крайней мере 2(д/2)' попыток для того, чтобы рассмотренным способом гарантировать исправление всех комбинаций стираний. 9.!О. Пусть р — нечетное простое, и пусть задан (2п,й)-код над бг'(р). Покажите, что укорачивание кода до длины и приводит к коду,:"который будет идеалом в алгебре многочленов по модулю Х" + 1, если все корни порождающего первоначальный код многочлена являются нечетными степенями некоторого корня порядка 2п.
9Л1. Для итеративного алгоритма декодирования двоичных кодов (теорема 9.12) покажите, что если 2„ — 1 — четное число, то 2(п+1) — 1+~ — либо следующее четное число (если 1, = 1„+~), либо наименьшее ранее неиспользованное нечетное число (если 1„чь'1+~). Аналогично, если 2п — 1„— нечетное число, то 2(п+ + 1) — 1„+~ равно или следующему нечетному числу, или наименьшему ранее неиспользованному четному числу. Таким образом, т — 1 на каждом шаге имеет разные значения, и существует единственный предшествующий шаг, иа котором т — 1 максим ально.
9Л2. Покажите, что в итеративном алгоритме для двоичных кодов на разных шагах для двух минимальных решений Ф >(Х) и Ф"~(Х) не может иметь место равенство 2и — 1„= 2т — 1 . Покажите также, что на одном и том же шаге п два решения имеют равные коэффцциенты старших порядков о~"~. 10 Коды с мажоритарным декодированием Подобно БЧХ-кодам, рассматриваемые в этой главе коды являются циклическими кодами над 6Р(д), исправляющими случайные ошибки.
В большинстве случаев они допускают весьма простое декодирование, но по сравнению с БИХ-кодами имеют несколько меньшую мощность для многих представляющих интерес значений а, А и д. Таким образом, с практической точки зрения во многих ситуациях эти два типа кодов конкурируют друг с другом. 10Л. Мажоритарное декодирование Как обычно, первым шагом декодирования является вычисление синдрома принятого набора символов длины и. Каждый символ синдрома и поэтому любая линейная комбинация символов синдрома представляют собой линейные комбинации некоторой совокупности принятых символов. Поскольку синдром каждого кодового слова равен нулю, декодер может определить значения д" —" линейных комбинаций подмножеств нз л ошибочных символов. Мажоритарное декодирование (206, 249) — это простой метод определения ошибочных символов по этим проверочным суммам (проверкам).
Понятие ортогональиых проверочных сумм является в мажоритарном декодировании основным. Пусть через зь ать ..., з, обозначены суммы различных символов вектора ошибок. Если символ е, вектора ошибок с весовым коэффициентом а из 6Р(д) вхо. дит в каждую проверочную сумму и ни один другой символ не входит более чем в одну проверочную сумму, то такие суммы называются ортогональными') относительно еь В более общем случае, если каждая проверочная сумма содержит символы еь е„...
..., ет с коэффициентами а, Ь, ..., 1 и нн один другой символ не содержится более чем в одной сумме, то проверочные суммы ортогональиы относительно суммы ае~ + Ьез+ ... + 1ео 1Ъ ) В этой главе термин «ортогональный» используется пе в его обычном ~мысле, связанном с понятием скалярного произведения (см. разд. 2.5). Действительно, два вектора, ортогональные относительно некоторого символа, не ортогональны в обычном смысле.
Например, в уравнениях (1О.1) э„ээ и зз ортогональны относительно суммы ае, + Ьеэ! э! = ае! + Ьсм вг = ае! + Ье, + сег, (10.1) эг=ае, +Ье, +де,+!ем Конечно, если проверочные суммы ортогональны относительно только одного символа, то коэффициенты, с которыми он входит в эти суммы, можно выбрать равными единице, поскольку код образует векторное пространство над 6Е(д). Причины рассмотрения ортогональных проверочных сумм разъясняет следующая теорема: Теорема 1О.1. Если для любого символа линейного кода суи!ествует по крайней мере й — 1 проверочных сумм, ортогональных относительно этого символа, то код имеет минимальное расстояние, авное по меныией мере й.
Л оказательство. Для того чтобы показать, что каждое ненулевое кодовое слово имеет вес не менее й, рассмотрим один из ненулевых символов кодового слова. Пусть это будет !-й символ, и обозначим 'первые й — 1 проверочных сумм, ортогональных относительно этого символа, через эп, э!ь ..., з!!л и. Все эти проверочные суммы равны нулю, так как проверяемое слово — кодовое.
В то же время каждая проверочная сумма имеет ненулевое слагаемое и, следовательно, должна содержать по крайней мере еще один (помнмо !-го) ненулевой символ. Из ортогональности проверочных сумм следует, что, помимо ю-го„существует не менее й — ! ненулевых символов. Следствие 1О.1. Если для циклического кода можно построить множество й — 1 проверочных сумм, ортогональных относительно какого-либо символа, то код имеет минимальное расстояние не менее й. Возможна и несколько другая интерпретация ортогональных проверочных сумм (10.1). Допустим, что существует й — 1 проверочных сумм, ортогональных относительно некоторой суммы е ошибочных символов.
Обозначим эти суммы через эь эь ..., эе !„ где э! = е+ е!. Пусть, далее, г=с+е, где через г и с обозначены соответственно принятые и переданные символы на позициях, соответствующих символам суммы е. Тогда й проверочных сумм с=с+в, — з, +с=с — е„ вЂ” эг+г=с — ем — зл !+! =с — е„, и зываются ортогональныжи оценками [260] суммы с переданных имволов. Этот подход может быть непосредственно распространен „а случай, когда проверочные суммы ортогональпы относительно линейной комбинации ошибочных символов.
Помимо определения нижней границы минимального расстояния, ортогональные проверочные суммы имеют еще одно назначе. иие: оии могут быть использованы для декодирования кода с помощью одного из вариантов декодера Меггита, описанного в ,л. 8. РассмотРим некотоРый линейный код, в котоРом длЯ каждого символа существует по крайней мере д — 1 ортогональных проверочных сумм, и предположим, что произошло не более [(г(— 1)/2] ошибок.
Если йй ошибочный символ равен нулю, то по крайней мере с( — 1 — [(д — 1)/2], т. е. не менее половины, проверочных сумм, ортогональных относительно этого символа, будут равны нулю. Так как рассматривается код над бг(д), то всегда можно выбрать коэффициент при 1-м символе равным единице. Если, с другой стороны, символ имеет значение о ~ О, то по крайней мере д — ! — ([(Й вЂ” 1)/2] — ), т. е. не менее половины, проверочных сумм будут также иметь значение о. Остальные ошибки могут влиять только на [(И вЂ” 1)/2] — 1 или меньшее число ортогональных проверочных сумм.
Таким образом, значение каждого символа вектора ошибки равняется значению, которое имеет абсолютное большинство проверочных сумм, ортогональных относительно этого символа; если же ни одно из (ненулевых) значений, принимаемых'проверочными суммами, не имеет абсолютного большинства, символ вектора ошибки равен нулю. Другими словами, истинное значение каждого переданного символа равно значению большинства его ортогональных оценок. На фиг. 10.1 изображен один из вариантов декодера Меггита (фнг.
8.5). Этот декодер может быть использован для декодирования циклического кода, имеющего для каждого символа г! — 1 ортогоиальных проверочных сумм. В этом варианте комбинационная логическая схема декодера Меггита реализована на схемах умножения в бг" (д) и одном мажоритарном элементе с г( — 1 входами. Изображенный на фиг. 10.1 регистр сдвига с обратной связью из (а — А) ячеек идентичен регистру, показанному на фиг. 8.2. Он производит умяожение принятого слова на Х"-» и затем делит РезУльтат на й(Х). Остаток после деления равен некоторому сдвигу синдрома и запоминается в регистре.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
