У. Питерсон - Коды, исправляющие ошибки (1267328), страница 69
Текст из файла (страница 69)
Таким об. разом, если 1„+! = 1„, то 1, ( 1„— 2 (и — и) . Ч. т. д. Локавательетво. По предположению и-(-рм- ! О, 5;ог! ! (+оп — ! = — ~ Д.~о, 1=а — и+ 1, а — и+2,...,а, 1=а+1. (9.61) Теорема 9.12. Пусть оьп(Х) — минимальное решение на и-м шаге, и пусть о~ >(Х) — одно из предшеетвуюи(их решений, 1 ( ~ т ( и, г й Ф'О, такое, что 2т — 1 имеет наибольшее значение Тогда минимальное решение на (и -1-1)-м шаге будет равно 1( оа(Х)+йй 'Х""- ' ' '(Х) й ~О В последнем случае оь'+н(Х) имеет степень 1г ы =шах [1„, 1 + 2(п — т)1. (9.63) Доказательство. Если а„= О, то о~"+П(Х), очевидно, будет минимальным решением, поскольку о<"~(Х) — минимальное решение.
Если же й„~ О, то, согласно лемме 9.7, о<"+Н(Х) будет решением со степенью 1„+ь определяемой выражением (9.63). Остается показать, что это решение минимальное. Если 1 > 1 + 2(п — т), то по лемме 9.7 1ьы =1 и о~"+п(Х) будет, очевидно, минимальным. Если же 1 (1 + 2(п — т), то 1вы =1 + 2(п — т), Допустим, что существует многочлен 7Х"+н(Х) степени а, где 1„~ а'«с. с-1 +2(п — т) или 2п — а > 2т — 1 .
Теперь, если й = 1„, по лемме 9.8 на некотором шаге т' существует решение с 2т' — 1 ° > > 2п — 1„. Но 2т' — 1 ° (2п — 1„, поскольку по предположению гп выбрано таким, чтобы 2т — 1,„было наибольшим для всех предыдущих решений, Таким образом, а ~ 1„.
Теперь, если а > 1„, то по лемме 9.8 а=1 ° +2(п — т') или п — а = 2т' — 1 . Следовательно, 2т' — 1 ° > 2т — 1; это противоречит предположению, что т выбирается так, чтобы максимизировать 2т — 1 . Таким образом, многочлен 1л +Н(Х) ие существует, и теорема доказана. Ч. т. д. 9.7. Исправление стираний и ошибок В некоторых случаях желательно, чтобы наряду с ошибками декодер исправлял и стирания. Если код имеет конструктивное расстояние аь и произошло е стираний и если йо = 21+ е+ 1, (9.64) то эти стирания вместе с ошибками, число которых не превосходит 1, могут быть исправлены.
(См. задачу 1.5.) Для декодера стирание в это ошибка, позиция которой известна, а значение может быть (а может и не быть) нулевым. В двоичном случае исправление комбинации ошибок и стираний осуществляется непосредственно. Сначала декодер пытается декодировать принятое слово, подставив на место стертых символов про- извольные значения, скажем нулевые.
Затем декодер подставляет вместо стираний дополнения этих значений и снова пытается декодировать. Предположим, что /, 0 ~ / ~ е, первоначальных предположительных значений стертых символов оказались неверными; тогда е — / их дополнений также будут неверными. Так как ш!и(!,е — /) ( е/2. то в одном из этих двух случаев общее число ошибок будет не больше (4,— 1)/2 н их можно исправить методом, описанным в равд. 9.4. В другом случае должно быть исправлено всего /+ шах(/, е — Л ошибок. Если оказывается, что эта сумма не превосходит (4~— — 1)/2, то при декодировании здесь также получится истинный ре.
зультат. Если же это не так, то общее число ошибок превосходит корректирующую способность декодера и, так как 2/+а~да, декодирование не приводит к истинному кодовому слову. Этот подход не может быть простым способом обобщен на недвоичные коды, поскольку каждый стертый символ может иметь уже д = 2 значений и требуется значительное число попыток, чтобы обеспечить правильность по крайней мере половины из ннх. (См. задачу 9.9.) Однако алгоритм, рассмотренный в равд.
9.4, можно изменить так, чтобы исправлять одновременно ошибки и стирания. Предположим, что произошло ч « / ошибок в позициях Хь Хь ..., Х„которым соответствуют ненулевые значения Уь Ум ... ..., У„. Далее допустим, что произошло е стираний в позициях (/!, (/з, ..., (/„которым соответствуют значения У„У„..., Р,. Теперь е и (/! известны декодеру, а У! могут быть (или могут не быть) нулями.
Кроме того, допустим, что выполняется условие (9.64), Первый шаг при декодировании состоит в вычислении из принятого многочлена г(Х) степенных симметрических функций е э1= «(и)= Х У!Х!+ Х У!(/!, и!0~~/! л!о+с(о 2. (966) ! ! ! 1 Снова, как и в равд. 9.6, пг, берется равным единице, хотя результаты могут быть обобщены непосредственным образом. Пусть выражение е Ц((/ — (/!) = ~ па(/' (9.66) ! ! а-о определяет элементарные симметрические функции номеров известных стертых позиций. Теперь определим модифицированные синдромы следующим образом: Т! = ~ оаЗ! м /= е+ 1, е+ 2, ..., И вЂ” 1. ь-а Подставив в последнее выражение (9.65) и (9.66), получим е о о е Т, = ~ „~: У!Х)-'+ ~ по ~: Г!~4-" = о-а $-! о-о о в е е =2'Ух!! 'Е Х' +ХУД! 'Х ои' " — а-а ! ! о а Из формулы (9.66) следует е пег!! =О, !'=1, 2, ..., е, -о поэтому Т! — — ~Е!Х„1=-е+1, е+2, ..., !1 — 1, (9„67) где о Е!= !'!Х,.
' ~ паХ! о-о Так как Х! Ф О и Х, чь 17ь то Е! чь О. Уравнения (9.67) связывают т неизвестных величин Х; с множеством !1а — е — 1 ) 2т известных степенных сумм. На 2-м н 3-и этапах общей процедуры декодирования, изложенной в равд. 9.4 и 9.5, был дан элегантный и легко реализуемый метод решения этих уравнений относительно Х!. После нахождения Х! остается вычислить т ненулевых значений У! и е, возможно, ненулевых значений Г!. Этн значения связаны с известными номерами позиций ошибок и степенными суммами уравнениями (9.65).
На 4-м этапе алгоритма исправления ошибок, рассмотренном в равд. 9.5, показано, что при заданных номерах позиций и степенных суммах первые т уравнений могут быть просто решены относительно т значений ошибок. Этот метод можно использовать здесь, если заменить т на т + е. Таким образом, любая комбинация т ошибок и е стираний может быть исправлена с помощью этой модификации итеративного алгоритма при условии„что БЧХ-код имеет конструктивное расстояние !(о) ) 2т+ е+ 1. Сложность декодера, необходимого для исправлеаия ошибок и стираний, незначительно превосходит сложность декодера, осуществляющего лишь исправление ошибок. Тем не менее она также растет как л1ода л.
9.8. Негациклические коды В сущности все исследования по кодам, исправляющим ошибки, основаны на метрике Хэмминга. Исключением являются негациклические коды Берлекэмпа (201, которые используют метрику Ли. (См. равд. 3.!.) Эти коды представля!от собой одну из форм БЧХ-кодов.
БЧХ-код, как и любой другой код с расстоянием Хэмминга г(, имеет расстояние Ли г(ь ~ е(. Если БЧХ-код над 6Р(р), где Р— простое число )5, имеющий длину 2п и скорость свыше '/е и определяемый корнями а', сея, ..., и" — ', укорачивается до половины своей естественной длины, то новый код имеет расстояние Ли, по меньшей мере равное е(.
Берлекэмп [20] показал, что если четные степени ех исключить из числа корней д(Х), то полученный код будет идеалом в алгебре многочленов по модулю Х" + 1 и иметь расстояние Ли, равное д, при условии е( ( р (см. задачу 9.10). Короче, расстояние Ли будет в 2 раза больше, чем расстояние Хэмминга, гарантируемое границей БЧХ. Кроме того, Берлекэмп [20] построил алгоритм декодирования для этих кодов, аналогичный тому, который используется при декодировании БЧХ-кодов (равд. 9.4 — 9.6). Этн коды превосходят по своим возможностям коды, использующие метрику Хэмминга, для каналов, в которых переход значения символа в соседнее происходит значительно чаше, чем другне типы ошибок. Замечания Коды, описываемые в этой главе, были получены независимо Хоквингемом [14Ц и Боузом и Рой-Чоудхури [29, 30].
Интересно, что коды, построенные ранее Ридом и Соломоном [250] и описанные в равд. 9.2, оказались частным случаем БЧХ-кодов. Результаты по определению истинного минимального расстояния БЧХ- кодов основаны на работе [167]. Первым был найден способ исправления ошибок, описанный в начале равд. 9.6. В большинстве случаев коды, методы кодирования и исправления ошибок обобщаются тривиальным образом, но эта схема исправления ошибок существенно зависит от того факта, что в двоичном случае при вычислении синдрома находятся некоторые симметрические функции номеров позиций ошибок.
Поэтому полученная Цирлером и Горенстейном схема декодирования, которая описана в равд. 9.4, была совершенно неожиданной. Математически их метод тесно связан с интерполяционной задачей [329]. Итеративные алгоритмы, представленные в равд. 9.5 и 9.6, были построены Берлекэмпом [2Ц, а алгоритмы для решения аналогичной совокупности уравнений над полем действительных чисел использовались ранее Тренчем [306].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
