У. Питерсон - Коды, исправляющие ошибки (1267328), страница 67
Текст из файла (страница 67)
Возьмем о)м (Х)=1. Если ошибок не было, то на любом шаге это будет реп)ением. Если произошло 1 ошибок, 1 ~(1((й — 1)/2, тогда не все Яр 1 ч,.1г-'21, равны нулю, поскольку принятый вектор не будет кодовым. Пусть ч обозначает наименьшее значение 1, для которого Я) ФО. Тогда о)ь)(Х)=о)" (Х)= ... =о< ')(Х), но й ) = 5, Ф О. Кроме того, 1ь= 1, ... =1, = О. Однако, так как Ет чь О но Бч-) = 3~-г =... О, не существует многочлена оы) (Х), удовлетворяющего уравнению Я +Я,о',»>+ ... =О. Поэтому на т-м шаге удовлетворяется т — 1,=0 уравнений, 1, должно быть равно т и ааа(Х) — произвольный многочлен степени 1 = т или.меньше. Выбор а<»!(Х) = ! является удовлетворительным. При о"-о(Х)=1, 1,=0, б~,=З чьО, о'»г(Х) = 1, 1» = О, г!» = Я»,, можно применить теорему 9.10.
Так как первые т — ! степенных сумм равны нулю, то из границы БЧХ следует, что комбинация ошибок имеет вес по меньшей мере». Позтому при п ( 2» решение не может быть окончательным и для получениея окончательного решения следует применить теорему 9.10. Рассмотрим следующие довольно искусственные определения: о~-о(Х)=1, 1,=0, б,=1, он(Х)=0, 1 =О, д =Яо Снова допустим, что 3, Ф.О, но Я, =0 для всех 1<». Тогда, применяя теорему 9,!О, получим ога(Х)=оп>(Х)= ... =Ф»-о(Х) и д,, =3 чь О„а также 1,=1, = ... =1,=0, и удовлетворительным выбором для оел(Х) будет многочлен паа(Х)=о' ' (Х) — б» 4,Хм в ~ поа п(Х)=1 — Я Х» (946) причем истинное значение 1» равно 1„= гпах (1,, (т — !) — ( — 1) + 1,) = т. Используя теорему 9.10, на каждом шаге будем получать истинные решения.
Начальные условия (9.45) удобнее для программирования, чем условия (9.44), так как не требуется определять, какие из Я; равны нулю. ' Пример. Рассмотрим декодирование кода Рида — Соломона, приведенное в качестве примера в равд. 9.4. Для рассмотренного там случая я~ — — ат. 8» = а'а, яз = аа, Зе= сгы, Юз= иы н Яа сс'4. Положив, как и в (9.45), а' п(Х)=1, 1,=0, г(,= 1, оо>(Х)=! 1,=0 ф,=Я =о' ~0 и применяя теорему 9.!О, получим о'в (Х)= ! + а»Х, 1, ! и д! = За - 1 + 8~ . а~ = аа, Возьмем теперь и = 1, т = 0 и, применяя снова теорему 9.10, получим а~в(Х)= ! + агХ+аза-'Х= 1+азХ 1, = шах (1„1 — 0+ 1с) = 1, И~ = аз.
Так как 1 — 1, = 0 — 1м то на следующем шаге одинаково приемлемы как т = 1, так и т = О. Выбор пт= 1 приводит к и,'н(Х)= ! +а Х+ а Х ° г(а=а > а выбор т = 0 дает пь (Х)=!+а"Х+а~Хт, ~1 =па, В любом слУчае 1з = гпах(1ь 1 '+ 2 — т) = 2 и на следующ шаге п=й,гп=2, 1ч=2, 4 (Х) ! 1 !АХ 1 1ЗХ2 и й4 = г(з = О. Многочлен о'(Х) — истинное значение п(Х), такое же, какое было найдено в равд. 9.4.
Так как уравнения (9.29) линейные, то любая линейная комби- нация по~~ (Х) + Ьа'„в (Х) является решением при условии, что а+ Ь = 1, так что свободный член равен 1. Можно выбрать а и Ь так, чтобы слагаемые с коэффициентами высших порядков взаимно уничтожились и азо<~ (Х)+ а"и„"(Х) = ! + АХ = а~в (Х). Последний многочлен также будет решением с 1з = 2, так как Зз+азЯ~ = О, но Я~+ азВ, Ф'О. Наконец, возьмем другой набор начальных условий (9.44): ам (Х) = 1, 1~ = О, о"'" (Х) = 1, 1, = 1, Тогда, применяя теорему 9.10, при и = 1, т = 0 получим о~в (Х)=! + азХ, ! = 1, сц=а'. Снова возможны два варианта: а = 2, т = 0 или а = 2, гп = 1', Первый вариант, как и прежде, приводит к о' ' (Х) = 1 + а Х + опХ дз = а ° (з 2, тогда как второй дает о'в(Х)=1+ аэХ, г(э=оп, 1з=2 Любой из этих многочленов о!Н(Х) приводит к единственному правильному многочлену о'(Х), являющемуся окончательным решением.
Этап 3. Определение номеров позиций ошибок. Если известны о~ для всех й 1 (1~ э (1, где т равно числу ошибок, которые в действительности имели место, то из уравнений (9.14) сравнительно легко определяются т номеров позиций ошибок. Необходимо просто подставить вместо Х все п возможных номеров позиций ошибок. Если о, + о,,Х+ ... + а,Л" '+ Х' 1х „= О, (9.47) то сс' — номер ошибки, в противном случае это не так.
Эта процедура может быть непосредственно реализована с помощью алгоритма поиска Цяня (49). Так как кодовые слова передаются начиная с символов старших порядков, удобно начинать проверку номеров позиций с а"-'. Элемент а"-' будет корнем многочлена от+ о -~Х+ ° + о~Х~ ~ + Х (9.48) тогда и только тогда, когда 1 будет корнем многочлена а от+а~ 'оч — 1Х+ ... + ао,Х +Х ° (9.49) Таким образом, для того чтобы проверить номер позиции, декодер вычисляет коэффициенты а'а,„ат 'о „..., ао, и затем находит их сумму. Если эта сумма равна 1, то а"-' — номер позиции ошибки, в противном случае это не так. для проверки номера и"-з каждгяй коэффициент а'о; должен быть умножен на а'. Затем новые коэффициенты складываются, и если их сумма равна 1, то й — а — номер ошибки, в противном случае второй принятый символ безошибочен.
Вообще и" 1 есть номер ошибки тогда и только тогда, когда Х аио;=1. Таким образом, на каждом шаге для того, чтобы получить следующее множество коэффициентов, необходимо 'лишь каждый 1-й (1 ~ 1~ т) коэффициент аио~ умножить на а*. Это вычисление очень легко реализовать на регистрах сдвига, описанных в равд. 7.2. Подробности даны в работе 149). Этап 4.
Вычисление значений ошибок (89). Значения У, ошибок могут быть вычислены с помощью уравнений, выводимых в этом разделе. Определим элементарные симметрические функции од номеров позиций ошибок Хь Хв ..., Х; ь Х;+„..., Хт как т-1 П(Х вЂ” Х~)=К оиХ (9.50) $ФГ с-о уравнение (9.!4) запишем в виде ч П (Х вЂ” Х,) = ~ о,Хч '. С-О где аО всегда равно 1. Из этих двух уравнений находим Ч вЂ” 1 ч (Х вЂ” Х») Х п»»Х' ' '= Х г»»Х" '. С-О С-О Приравнивая коэффициенты (9.51) ос = о»с Х»а» <с+1), (9.52) получаем возможность при о;О= 1, исходя из известных Хс н ов рекурсивно определять о ь Теперь ч-1 — ч — ! о»»Ю вЂ” с = Х ос ~ сч'»ХГ» = Х У, ~'" а»»Х -О С-О »-1 ! ! С О что, согласно формуле (9.50), дает ч-1 ч Е о„З, = Е У,Х, Ц (Хс — Х ).
»-О ! ! си~» В сумме справа не равно нулю лишь то слагаемое, для которого с = 1, и поэтому ч-1 о»»Б -с = Г»Х» П (Х» Х ) О ~чЧО» н, снова используя равенство (9.50), получим 'ч — ! ч-1 Х вЂ” —,Х г»»»8 -с = 1» 0»»Х» О С-О Значения ошибок, таким образом, могут быть вычислены по формуле ч-1 сс»»э" С-О у»= ~, а»»Х»ч с Пример. В примере декодирования кода Рида — Соломона, приведенном в равд. 9.4, 31 =та», 32=а'~, о, =в'~, ос=а'з, Х, =аз и Х,=а'О. Из уравнения (9.52) находим о!Π— — о2Π— — 1, оп —— = о, + Х, = а'О и о„= и, + Х2 = оз.
Затем по формуле (9.53) получаем а1,32+ ссс!5! 1 у 2 =а Э в»ОХ! + впХ Важно, по крайней мере приблизительно, определить сложность устройства, необходимого для декодирования БЧХ-кодов. На этапе 1, состоящем в вычислении взвешенных степенных сумм, требуется 2(о д-ичных регистров сдвига с обратной связью, содержащих ит ячеек. Вычисление обычно начинается, как только слово поступает в декодер, и для полного завершения этого процесса требуется и тактов. Этап 2 — определение нормализованных элементарных симметрических функций — выполняется за 2(о шагов.
На каждом шаге, вообще говоря, необходимо вычислить новое решение на основе предыдущего решения и одного из более ранних решений. Каждый многочлен имеет степень 1о или меньше. Поэтому к основному арифметическому устройству, которое может делить'), складывать, вычитать и умножать в бг(д ), необходимо добавить вспомогательных арифметических устройств, способных лишь складывать н умножать. Поэтому потребуется приблизительно 4ит1о дополнительных ячеек регистра сдвига. На каждом шаге выполняется одна операция умножения или сложения, так что для этапа 2 необхбдимо 2ит1а тактов.
Этап 3 в вычисление номеров позиций ошибок в выполняется за и шагов (илн, возможно, только за й шагов, если исправляются только информационные символы). Каждый шаг состоит из умножений на фиксированный элемент и сложении. Таким образом, для этого этапа необходимо (а регистров и требуется приблизительно ти тактов. Этап 4 — вычисление значений ошибок — включает в себя вычисление ая по формуле (9.50) и затем определение значений ошибок по формуле (9.53).
Так как имеется 1о арифметических устройств, то для каждой ошибки первая из этих операций требует 2пМа тактов, а вторая — 4тго тактов. Таким образом, полное число необходимых тактов равно блт1о. Кроме того, дополнительно требуется 1„регистров сдвига с и ячейками. Рассмотренные оценки приведены в табл. 9.2.
Для примитивных БЧХ-кодов ги = 1оКчи. Если го выбрать равным аи, где 0 ( а (0,25, то Число ячеек регистра =и(2+ 7а!ояри), Число тактов =и(1+ 1одаи(1+ За) ). Таким образом, число операций и размер декодера растут как и1оа„и. При больших и сложность растет с увеличением длины блока лишь немного быстрее, чем линейно. ') Недавно Бартон 136) нокааал, что па крайней мере в двоичном слутае делелне не является необходнмым. таблица 9.2. Сложность основных этапов декодирования НЧХ-кодов с испольяованием спепиаливированных вычислительных устройств ячейка петястпа Операция Этап 1 вычислевие 81 Этап 2 вычисление Ш Этап 3 вычисленке Х~ Этап 4 вычисление Г; напоминание слова 2тгс 4оИя вихр тахо 2п Предыдущие вычисления делались в предположении наличия 1о арифметических устройств.
При использовании универсальной ЭВМ одно арифметическое устройство должно выполнять работу 1о устройств и число операций будет расти как л'1ояч п. 9.6. Упрощения в двоичном случае Декодирование двоичных БЧХ-кодов проще декодировании не- двоичных кодов в трех отношениях. Во-первых, проще используемые прн этом схемы, так как цифровые устройства основаны на двузначной логике. Во-вторых, поскольку все ошибки имеют значение 1, 4-й этап алгоритма не нужен. Наконец, 2-й этап можно выполнить за то, а не за 21о шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
