У. Питерсон - Коды, исправляющие ошибки (1267328), страница 61
Текст из файла (страница 61)
Так как минимальное расстояние не меньше чем 21+1 и для любого линейного кода г(» ~и — й+1, то отсюда вытекает, что для таких кодов Оказывается, что эти коды могут быть представлены в циклической форме. Вычет многочлена 1(Х)= 12 1Х" '+ 12-2Х"-2+ ... ... +11Х+ 12 по модулю (Х вЂ” а1), который является элементом поля 6г (д'"), может быть получен нз выражения 1(Х) = 1', + д1 (Х) (Х вЂ” а') в виде (Х)[х а Пусть порождающая матрица (п,й)-кода с символами из поля 6Е(д ) имеет вид (аь ') (аь ') ... ць 1аа (Оь-2)а 1 (Пь-2)а 2 Пь-2 110 (8.58) оа-1 па — 2 о1 оа Умножая матрицу 6 на информационный вектор (12 112 2...12), получим набор длины гк (1(Х)[Х Л-1> 1(Х)[Х „П-2, „ 1(Х)[Х , 1(Х)[Х 11= = [г„„г„2, ...„г„га!, (8.59 являющийся кодовым словом в коде, основанном на китайской теореме об остатках.
Однако матрица 6 является порождаю1цей матрицей циклического (п,й)-кода, для которого и1, а2, ..., 22" ' — корни Й(Х). Фактически это код Рида †Соломо, который подробно обсуждается в следующей главе. Описанная в этом разделе процедура декодирования, очевидно, неосуществима ни для каких кодов, за исключением самых коротких. При каждом декодировании декодер проводит Сь операций. К счастью, был найден более просто реализуемый метод декодирования этих очень мощных кодов; этот метод также обсуждается в гл.
9. Поскольку символы поля 6Г(о™) могут быть представлены в виде наборов длины л1 над полем 6г(д), то эти коды идеально подходят для исправления кратных пакетов ошибок. Этот вопрос обсуждается в гл. !1. Не обязательно рассматривать линейные множители в расширении поля; многочлены более высоких степеней над 6Р(д) также дают интересные коды. Однако эти коды не являются столь мощными, как коды, основанные на линейных множителях, т. е. коды Рида — Соломона.
Пример. Существует б двоичных многочленов степени 4„которые попарно взаимно просты. Выберем А =. 8 и предположим, что п вились две или меньшее число ошибон. Число правильных определителей для г(Х) по меньшей мере равно С~л 2=6, ~гда как число определителей для отдельных неправильных информационных многочленов равно самое большее ч С;;„, =3. Следовательно, для этого (24,8)-кода г() 5. Кроме того, заметим, что если вычеты передаются в виде блоков, то пакет ошибок длины 5 или меньше может воздействовать самое большее на 2 блока, так что этот код обладает способностью исправлять пакеты ошибок по меньшей мере длины 5. Замечавня Изучение циклических кодов было начато Прейнджем [243,245].
Многие работы, посвященные специфическим циклическим кодам, цитируются в следующих трех главах; некоторые из идей, представленных в этой главе, прямо или косвенно исходят из этих источников. Эквивалентность циклических кодов и идеалов была замечена независимо Прейнджем, Питерсоном [232] и Касами [158]. Подход, связанный с ассоциированными многочленами, был развит Мэттсоном и Соломоном [213]. Результаты равд. 8.6 собраны Ченом [42]. Метод кодирования, основанный на использовании регистра сдвига, состоящего из й ячеек, по существу эквивалентен илес использования последовательностей, вырабатываемых регистрами сдвига, в качестве кодовых векторов и появился впервые в работах Грина и Сан-Суси [127] и Прейнджа [244]. Способ кодирования с использованием регистра сдвига, состоящего из и — й ячеек, был найден Питерсоном [232], а тот факт, что этот способ может быть видоизменен таким образом, чтобы использовать схему, эквивалентную схеме деления, был обнаружен Меггитом и Эйбрамсоном.
Теорема 8.7 и следствия из теоремы 8.6 относительно обнаружения ошибок циклическими кодами получены 5раУном [34]. Использование этих идей в практических задачах обнаРужения ошибок описано в работе [86]. Грин и Сан-Суси [!27] предложили использовать последовательности максимальной длины для исправления ошибок, а Цирлер [341] указал на связь таких последовательностей с кодами Рида — Маллера. Коды Хэмминга были ранее изучены Эйбрамсоном [2], Элспасом [73], а также Стерном и Фридлендом [287] как циклические коды. Стерн и Фридленд рассматривали их с точки зрения линейных схем и нашли способ их реализации, описанный в задаче 8.5.
В их системе код не является систематическим, т. е. информационные символы не появляются в кодовом векторе в неизмененном виде. Поэтому, помимо устройств для исправления ошибок, приходится пользоваться декодирующим фильтром. Разумеется, нет никаких существенных причин для того, чтобы считать, что подход, развитый в этой главе, приводит в каждом случае к более хорошему методу декодирования. Основной декодер из равд.
8.9 описан Меггитом [217). Метод вылавливания ошибок, вероятно, впервые был разработан Прейнджем; кроме того, он ввел перестаповочное декодирование как вариант метода вылавливания ошибок. Этот метод декодирования независимо найден Мак-Уильямс [1961 К идее вылавливания ошибок с «окнами» независимо пришли Касами [164) и Митчел и др. [223). Равд. 8.10 основан на работе Шатка. Основным источником материала по симметрии кодов являются работы Прейнджа. Теоремы об аффинных перестановках получены Касами [167). Доказательство того факта, что произведение циклических кодов может быть циклическим, впервые дано Вуртоном и Уелдоном [37) и было подсказано результатом задачи 11.2.
Изящная трактовка произведения циклических кодов, и в частности теорема 8.!9, принадлежит Лину [184). Квадратично-вычетные коды были впервые рассмотрены Прейнджем [244), а важные дальнейшие результаты получены Глисоном [108), Плесе [239) и Ассмусом, Мэттсоном и Туриным [1Ц. Квазициклические коды впервые рассмотрены Таунсендом и Уелдоном [305), а дальнейшему их изучению посвящены работы [42, 142, 159). Равд. 8.15 основан на работе Стоуна [29Ц.
Задачи 8.1. Циклический код порожден многочленом п(Х) = Ха+ +Хт+Ха+Х4+ 1 а) Покажите, что длина этого кода равна 15. б) Найдите для этого кода порождающую матрицу и проверочную матрицу в модифицированной приведенно-ступенчатой канонической форме. в) Постройте линейную переключательную схему для кодирования, содержащую й = 7 ячеек, и аналогичную схему, содержащую и — й = 8 ячеек.
г) Покажите, что и, иа, аа и ૠ— корни многочлена д(Х), если а — корень многочлена Х«+ Х+ 1. (Ср. с табл. 6.1.) д) Постройте схемы для вычисления значений г(1), г(и) и г(иа) для любого полученного вектора [г(Х)). 8.2. Покажите, что минимальный вес двоичного циклического кода длины и, порожденного многочленом д(Х), равен самое меньшее 3, если и†наименьшее целое число, при котором мнагочлен Хи 1 делится на д(Х).
Верно ли это утверждение для недвоичных кодову 8.3. Предположим, что многочлен д(Х) порождает циклический од длины и над полем 6г"(д) и что и не делится на д. Покажите, что вектор, состоящий из одних единиц, принадлежит коду тогда „только тогда, когда многочлен д(Х) не делится на Х вЂ” 1. 8.4. Пусть д*(Х) — многочлен, двойственный к многочлену я(Х).
а) Покажите, что коды, порожденные многочленами д(Х) и д*(Х), эквивалентны, б) Покажите, что если д(Х) = д"(Х), то код, порожденный многочленом д(Х), обладает тем свойством, что если ч = (ае,аь... , а,) — кодовый вектор, то и ч* = (а„ь а м..., аа) — тоже кодовый вектор. 8.8. Пусть а — примитивный элемент поля 6г(д'"), и пусть и =(4'" — 11)/(д — 1). Покажите, что а — примитивный элемент поля 6г(д).
Рассмотрите матрицу Н=(цл ! цл 2 и код, совпадающий с нулевым пространством этой матрицы. (Нулевое пространство матрицы Н является укороченным цикли- ческим кодом, так как а" Ф 1. Это циклический код длины д — 1, в котором используются только и компонент низших порядков,) Покажите, что минимальное расстояние нулевого пространства матрицы Н равно самое меньшее 3. Постройте регистр сдвига для кодирования, содержащий т ячеек. Постройте систему для деко- дирования, аналогичную системе нз равд.
8.9, и укажите необхо- димые схемы с регистрами сдвига. 8.6. а) Покажите, что при нечетном и никакой двоичный цикличе- ский код не содержит среди кодовых слов набор, состоящий из одних единиц, если этот код включает проверку на четность по всем символам. Покажите также„что этот набор является кодовым словом, если код не включает проверку на четность по всем сим- волам.
б) Покажите, что при четном и справедливо противоположное утверждение, 8.7. Используя поняТие нормального базиса (равд. 8.14), по- стройте квазициклический (8„3)-код из табл. 8.3 на основе (7,4)- кода Хэмминга. 8.8. Пусть а — примитивный элемент поля 6Е(ч™") и р = в» '. Тогда порядок р равен и = (д~й — 1)/(д — 1). (См. равд. б.б.) Пусть й(Х) — минимальная функция для р и д(Х) =(Х" — 1)Ф(Х). а) Покажите, что если ч — кодовый вектор из кода, порожден- ного многочленом д(Х), и если (1,у) — различные пары, где 0» 1 и, а у — элемент 6Р((1), то векторы, полученные из вектора ч циклическими сдвигами на 1 разрядов и умножением результата сдвига на скаляр у, являются различными кодовыми словами.
б) Используя результат, полученный в п. а), покажите, что все ненулевые кодовые слова в этом коде имеют один и тот же вес. Этот код является нулевым пространством кода Хэмминга. Из этого результата и тождеств Мак-Уильямс может быть получено распределение весов кодов Хэмминга, (См. задачу 3.22.) 8.9.
Пусть С = (1Р) — порождающая матрипа циклического кода. Покажите, что если многочлен Ь(Х)=Х + Ь~,Х~ '+ ... + Ь,Х+ 1 является проверочным многочленом для этого кода, то первый столбец матрицы Р равен (1,Ььйм...,йь,)т. 8.10. Покажите, что если 1( и!Ь, то любая комбинация из л символов веса 1 или меньше будет содержать по меньшей мере Ь последовательных нулей. Покажите, что если 1 ) п)Ь, то найдется по меньшей мере одна комбинация веса й которая не будет содержать Ь последовательных нулей. 8.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
