У. Питерсон - Коды, исправляющие ошибки (1267328), страница 56
Текст из файла (страница 56)
В случае неудачи восстанавливаем первый символ, меняем на обратный второй символ и снова пытаемся декодировать слово. (Для кода с символами из бг'(д) необходимо испытать все д — 1 возможных значений ошибки на каждом шаге.) В конце концов некоторый неправильный символ будет заменен иа обратный, после чего остальные 1 — 1 ошибок могут быть циклически сдвинуты в некоторую часть слова, содержащую п — А символов.
Затем для исправления оставшихся ошибок можно применить процедуру вылавливания ошибок. Если первоначально появилось 1 или меньше ошибок, то в результате добавления еще одной ошибки получевное слово оста- нется на расстоянии, равном по меньшей мере 1, от любого другого кодового слова. Поскольку пороговый элемент имеет порог 1--1, го неправильное декодирование не может произойти.
Этот метод непосредственно обобщается на случай, когда одновременно заменяются на обратные 2 символа, 3 символа и т. д.„ при этом всегда требуется лишь немного оборудования. К сожалению, время, необходимое для декодирования, очень быстро увеличивается с ростом числа «дополнительных» ошибок, которые должны быть исправлены. Таким образом, так же как и для метода вылавливания ошибок и только что описанных его модификаций область возможных применений этого метода несколько ограничена. 8.10. Укороченные цпклические коды Поскольку циклические коды порождаются делителями много- члена Х" — 1, то для большей части значений и и А имеется относительно мало кодов. Поэтому естественно попытаться найти среди линейных кодов такие коды, которые хотя и не являются в действительности циклическими, но обладают похожей математической структурой и столь же легко реализуются.
Два таких класса кодов представлены в этом разделе и в равд. 8.14. При заданном линейном (и, А)-коде всегда можно построить линейный (л — й А — 1)-код, заменяя ! первых информационных символов нулями и исключая их из кодовых векторов. В случае циклического кода это соответствует исключению первых 1 строк и столбцов из порождающей матрицы или первых 1 столбцов из проверочной матрицы.
Полученный таким образом код не будет, однако, циклическим кодом, потому что теперь циклический сдвиг кодового вектора не всегда является кодовым вектором. Такой код называется укороченным циклическим кодом. Пример. Если в (7,4)-коде в примере из равд. 8.2 опустить первый информационный символ, то получится (6,3)-код с порождающей матрицей С и проверочной матрнцей Н: 100011 01!100 С= 010111 , Н= 110010 001101 1!1001 Векторы (001101), (011010) и (110100) принадлежат коду, однако вектор (101001), который получается при следующем циклическом сдвиге, ие принадлежит нулевому пространству матрицы Н. Укороченный код обладает по крайней мере столь же болыпим минимальным кодовым расстоянием, как и код, из которого он получен, и может исправлять любой пакет ошибок, который исправляет первоначальный код.
Действительно, поскольку при укорачиванин число смежных классов остается неизменным, то укороченный код может исправлять соответственно укороченный вариант любой комбинации ошибок, исправляемой первоначальным кодом, Еолее того, для декодирования обоих кодов можно использовать одни н те же схемы при единственном условии, что каждому полученному слову укороченного кода всегда приписывается спереди нулей. В теореме 8.1 утверждается, что циклический код является идеалом в алгебре многочленов по модулю Х" — 1.
Естественным обобщением является код, совпадающий с идеалом по модулю некоторого другого многочлена 1(Х). Такой код называется асевдоциклическим кодом. Следующие две теоремы показывают, что класс укороченных циклических кодов и класс псевдоциклических кодов совпадают. Теорема 8.9.
Любой асевдоциклический код с минимальным весом, большим 2, является укороченным циклическим кодом, Доказательство. Пусть 1(Х) — многочлен степени и; рассмотрим некоторый идеал в алгебре многочленов по модулю 1(Х), т. е. псевдоциклический код. Тогда в соответствии с утверждениями теорем 6,9 и 6.10 существует нормированный многочлен д(Х), порождающий идеал, и вектор (а„„а„м ..., ас) принадлежит идеалу тогда и только тогда, когда многочлен а(Х) = а„,Х"-'+' + аь аХ"-'+ ... + а, делится на д(Х). Пусть и' — наименьшее целое число, при котором многочлен Х" — 1 делится на д(Х).
Тогда и') а, так как иначе вектор (Х" — 1) был бы кодовым вектором веса 2. Поэтому многочлен а(Х) порождает циклический код длины и', причем вектор (а„ь а„м ..., ас) принадлежит этому коду тогда и только тогда, когда многочлен Г(Х) =а„ 1Х" ' + + а„ хХ + ... + ае делится на Ы(Х). Если укоротить этот циклический код, оставляя только те кодовые векторы, у которых все компоненты а„,а„+ь ..., а„ 1 равны О, н вычеркивая эти компоненты, то получится в точности тот же псевдоциклическнй код.
Ч. т. д. Теорема 8.10. Любой укороченный циклический код является псевдоцикл ическим кодом. Доказательство. Предположим, что многочлен д(Х) порождает циклический код длины а'1 рассмотрим укороченный циклический код длины и, полученный из этого кода. Равенство (6.4) можно переписать в виде (8.24) Х"=д(Х)д(Х)+ г(Х), где г(Х) — многочлен степени, меньшей степени д(Х). Положим 1(Х) = Х" — «(Х) и рассмотрим алгебру многочленов по модулю 1(Х). Из равенства (8.24) видно, что многочлен 1(Х) делится на многочлен я(Х). По теореме 6.10 многочлен д(Х) порождает идеал и, следовательно, псевдоцнклнческнй код, который, как нетрудно проверить, совпадает с рассматриваемым укороченным циклическим кодом. Ч.
т. д. Интересно отметить, что большинство наиболее известных кодов, исправляющих случайные ошибки, являются укороченными циклическими кодами. (См., например. табл. 5.4.) Циклический код, укороченный на 1 символов, может быть декодирован посредством тех же схем, которые используются для декодирования первоначального кода; необходимо только предпослать укороченному слову 1 нулей. Однако декодирование можно осуществлять быстрее, если вместо вычисления синдрома поли- нома Х" — ьг(Х), как следовало бы сделать для циклического кода, вычислять синдром полинома Х"-~+мг(Х). Лля случая декодера Меггита (фнг. 8.5) это означает, что первый полученный символ Х"-*'-' должен быть первым символом, подлежащим исправлению посредством комбинационной логической схемы.
Пусть з(Х) обозначает синдром полинома Х"-"+'(Х). Тогда з(Х) =Х" ьыг(Х)+ д(Х)д,(Х). (8.25) Пусть, далее, в качестве многочлена 1(Х) выбран многочлен 1 (Х) Х ьы + ьГ (Х) дэ(Х) (8.26) причем степень )(Х) меньше степени д(Х). Из соотношений (8.25) и (8.26) получаем г(Х)1(Х) =з(Х)+ 8(Х) Чд(Х). (8.27) Таким образом, предварительное умножение на Х"-"+' может быть проведено просто путем умножения получешюго многочлена на 1(Х), что осуществляется сдвигами его в регистре синдрома. Пример. Многочлен д(Х) = Х'+ Х+ 1 порождает двоичный (15, 11) -код Хэмминга, исправляющий одну ошибку. Предположим, что требуется укоротить этот код на 5 символов, с тем чтобы получить (! Р,б) -код. Остаток от деления Х" ь+з = Х' на д(Х) равен ~ (Х) = Хз + Х = Хэ + (Хз + Хэ + Х) (Хэ + Х + 1). На фнг.
8.7 показана схема, которая используется для умножения полученного набора длины 1Р на ('(Х), вычисления синдрома фнг. В.т. декодер Меггнта дан укороченного (10,6)-кода Хаммннга. и исправления одной ошибки с помощью метода вылавливания ошибок, описанного в предыдущем разделе. (См. фиг. 8.6 и связанный с ним пример.) 8.11. Симметрия кодов Для циклических кодов циклическая перестановка символов любого кодового слова превращает его в другое кодовое слово и, следовательно, циклическая перестановка символов совокупности всех кодовых слов переводит ее в ту же самую совокупность кодовых слов. Таким образом, циклические коды инвариантны относительно циклических перестановок. Другие коды являются инвариантными относительно других перестановок, а некоторые циклические коды инвариантны относительно некоторых нециклических перестановок.
В этом разделе представлена общая теория симметрии кодов такого вида. ПУсть чеРез к', обозначен гРУпповой (и, й)-код, а чеРез )гав нулевое пространство кода кь и пусть Р— некоторая перестановка и символов, а ч;Р— вектор, который получается после применения перестановки Р к и компонентам вектора ть Перестановку Р можно рассматривать также как матрицу перестановки, в каждой строке и в каждом столбце которой содержится по одной единице, а все остальные элементы равны нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
