У. Питерсон - Коды, исправляющие ошибки (1267328), страница 60
Текст из файла (страница 60)
Проиллюстрируем это на примере двоичного (12, 4) -кода. Пример. Наилучший двоичный (12,4)-код имеет минимальное расстояние 6. (См. табл. 5.4.) Существует квазициклнческий код с теми же параметрами; порождающая матрица этого кода имеет вид 111 011 000 00! 001 111 О!1 000 000 001 111 011 011 000 001 111 Кодирование для этого кода можно производить с помощью регистра сдвига с й = 4 ячейками, изображенного на фиг. 8.8.
Этот регистр работает следующим образом: после ввода четырех информационных символов в регистр ключ 2 закрывается, ключ 1 открывается, а выходы двух двоичных сумматоров равны двум проверочным символам в первом блоке из трех символов кодового слова. Символы этого блока затем поступают в канал в обычном порядке: сначала информационные, а потом проверочные. Затем происходит один сдвиг регистра, и процесс повторяется. В силу свойства квазицикличности следующие два проверочных символа снова появятся па выходах сумматоров.
Кодирование заканчивается, когда последний информационный символ будет считаи в данном случае после четырех сдвигов. Поскольку квазициклический код не является систематическим в такой декодер обычно требуется вводить дополнительный ре гистр сдвига с А ячейками для хранения информационных симво Фиг. 8.8. Кодер с к ячейками для квааиииклического !!2, 4)-кода. лов следующего блока до тех пор, пока не закончится кодирование, Этого затруднения можно избежать„ если использовать эквивалентный систематический код. Кроме того, кодирование для квазициклического кода можно проводить с помощью регистра, содержащего и — м-ячеек. (См. задачу 8,18.) Порождающая матрица квазициклического (тпо, пйо) -кода вида (8.54) может быть представлена в приведенной ступенчатой форме посредством перестановок столбцов.
Например, порождающая матрица (15, 5)-кода БЧХ с порождающим многочленом Х'о+Х'-(-Ха+Ха+Ха+Х+! может быть записана в виде 100 001 010 011 011 011 100 001 010 011 011 011 100 001 010 010 01! 011 100 001 001 010 О!1 011 100 Столбцы 1,4,7,10 и 13, затем 2,5,8,11 и !4 и, наконец, 3,6,9,12 и 15 образуют три циркулянтные матрицы, как это видно из следующего соотношения: 10000 00111 01011 01000 10011 10101 00100 11001 !1010 00010 11100 01101 00001 01110 10110 Квазициклические коды в таком виде изучались различными авторами.
В результате было обнаружено несколько довольно мощ. ных кодов, исправляющих случайные ошибки. В табл. 8.3 пере- Таблица 8.3. Некоторые двоичные клазициклические (л, л/2)-коды. Каждый из неречисленных кодов обладает наибольшим значением л среди кзазициклическнх кодов той же длины цри ге=0,5 Порождающаи строк» циркулиита(а восьмеричном иредстаалелниг Минимальное расстои- ние Л длина л числены квазициклическне 1п,п12)-коды при различных значениях и, обладающие наибольшим минимальным расстоянием среди квазициклнческих кодов 1421 Кроме значений и н е1, в восьмеричной форме приводится верхняя строка цнркулянтной матрицы, которая полностью определяет матрицу чи.
Заслуживает внимания тот факт, что во всех исследованных до сих пор случаях на этих кодах, обеспечивающих скорость передачи, равную 'гт„достигается наибольшее известное значение минимального расстояния в классе всех линейных кодов с теми же самыми значениями и и /г. В свете этого последнего замечания было бы желательно привести здесь методы построения квазицнклических кодов; к сожалению, только один метод построения квазициклическнх кодов был известен автору.
Хотя эти самоортогональные квазнциклические коды ~3051 могут быть декодированы посредством очень простого мажоритарного декодера, они обладают относительно малым минимальным расстоянием. Доказано существование очень длинных, хотя и не сколь угодно длинных, двоичных квазициклических кодов, для которых достигается граница Гилберта [441 Для этих кодов, обладающих невы- рожденными циркулянтными матрицами, достигается также гра- 6 1О 12 14 16 18 20 22 24 26 28 30 '32 34 36 38 40 42 3 7 7 7 7 27 117 57 267 573 653 727 2!67 557 557 573 557 5 723 14 673 3 4 4 4 4 5 6 6 7 8 7 8 8 8 8 8 8 9 10 ница вероятности ошибки случайного кодирования с вычеркиваниями. (См. равд.
4.2,) !(вазицикяические коды имеют интересное представление при помощи многочленов. Рассмотрим квазициклический (2й„й) -код а систематической форме, и пусть С вЂ” циркулянтная матрица, которая задает этот код. Если обозначить через ! информационный вектор, подлежашии кодированию, то = 1С = !1 1С!. Пусть, далее, через !(Х) обозначен информационный вектор в форме многочлена, а через с(Х) — верхняя строка циркулянтной матрицы С. Очевидно, остальные строки матрицы С имеют вид Хс (Х) (апой Х вЂ” 1), Х'-с (Х) (шоб Х вЂ” 1), ..., Хь 'с (Х) (гпод Хь — 1), Нетрудно показать, что алгебра циркуляптных матриц порядка т~(т изоморфна алгебре мпогочленов по модулю Х~ — 1 и что умножение вектора 1 па циркулянтную матрицу С эквивалентно умножению многочлена !(Х) на многочлен с(Х) по модулю Х" — 1.
Следовательно, многочлен о(Х) имеет вид [!(Х), !(Х) с(Х)!. (8.55) Таким образом, кодовое слово квазициклического кода можно рассматривать как информационный многочлен, за которым следует кодовое слово циклического кода длины А, порожденного наибольшим обшим делителем многочленов с(Х) и Х" — 1. Некоторые циклические коды близко связаны с квазициклическими кодами. Рассмотрим, например, квадратичпо-вычетный (17,9)-код, минимальное расстояние которого равно 5. Пусть а— корень многочлепа Ха+ Х'+ Ха+ Х+ 1. Положим р = а'з.
Тогда ч(Х) = т(р) = Ха+ Хт+Хз+ Ха+ Ха+ Х+ 1. Проверочная матрица этого кода может быть записана в виде 1! (р~зрмрнр~з(!ый~~р~зВзВз(!трзр~р~рзрзр~рч) В соответствии с изложенным в приложении В а и сопряженные элементы а, а, аз, ..., аз являются линейно независимыми. Таким образом, р можно представить как линейную комбинацию элементов такого базиса, который принято называть нормальным, а виде !3 = О + ан + ан + ам + ан + О + ан .+ О, и по теореме 6.14 сопряженные элементы являются циклическими сдвигами этого многочлена, т.
е. (у=ав+ам+ ан+сР'+О+а~'+О+О, р'=(У=О+ О+а" +ам+а~+в~+а' +а~". Можно доказать, что 5' = ат + сФ. Тогда сопряженные элементы для рз являются циклическими сдвигами набора длины 8: 00! 00001. 27 Можно показать, что корень рв представляется в виде а' +а' + +а~+а" +а~+а' +а- '+а~. (См. задачу 823) Таким образом„ матрица Н преобразуется к виду !( [[5< 513Р! 55 1 658[145251[ [Р %565115ИР7512фЯ 50) 100 1 Следовательно, (17,9)-код с одним исключенным информационным символом эквивалентен квазициклическому (16, 8) -коду.
Поскольку С,— невырожденная матрица, то матрица [С,С) может быть приведена к ступенчатой канонической форме путем умножения ее слева на матрицу, обратную к Сь Известно, что любое конечное поле обладает нормальным базисом [7). Поэтому порождающая матрица любого циклического кода может быть разложена по циркулянтным матрицам, хотя многие из них оказываются тривиальными. После этого, удаляя столбцы, соответствующие элементам, порядок которых меньше чем и, получим порождающую матрицу квазициклического кода.
Однако может оказаться, что нельзя представить такой код в форме систематического кода. 8.15. Коды, основанные на китайской теореме об остатках Пусть через !(Х) обозначен многочлен степени й — 1 или меньше с символами из поля ОР(д'"), а через т;(Х) — многочлен степени 4 с символами из того же самого поля. Можно построить интересный класс кодов на основе следующего варианта китайской теоремы об остатках «29!).
Теорема 8.20. Многочлен !(Х) может быть восстановлен на основе остатков т;(Х)впю'(Х)(шобт;(Х)), 1=1, 2, ..., и, (8.56) если многочлены т~(Х) попарно взаимно просты и с(~ > й — 1. (8.57) 01011110 00101111 10010111 11001011 11100101 11110010 01111001 10111100 10000 01000010 00100001 10010000 01001000 00100100 00010010 00001001 1 1 1 1 = [С,С,). 1 1 1 Доказательство. Любые два решения 1,(Х) и !э(Х) совокупности сравнений (8.56) сравнимы по модулю ш (Х) =игл, (Х), по- 3 ! скольку разность й(Х) — !з(Х) делится на т(Х) тогда и только тогда, когда она делится на каждый многочлен и;(Х). Так как в каждом классе вычетов по модулю ги(Х) существует только один многочлен степени, меньшей чем й, то существует только одно решение совокупности сравнений (8.56), которое и есть искомое решение. Ч.
т. д. Эту теорему используем для построения класса кодов, исправляющих случайные ошибки, над полем ОР(д ). Выберем в ка- /П т~ честве т';(Х) множители многочлена Хч — 1 в бр(д ). Поскольку этот многочлен в бР(д™) полностью разлагается на множители, то и;(Х)=(Х вЂ” а'), 1=6, 1,, !'" где а — примитивный элемент поля Сг (д ). Затем вычислим а = д™ вЂ” 1 вычетов информационных много- членов 1(Х), степень которых меньше чем А.
Совокупность этих многочленов образует линейный (и, А) -код с символами нз поля бг(д ). Декодирование можно проводить следующим образом. Предположим, что появилось ! ошибок, так что правильно получены только и — ! вычетов. Далее, !(Х) полностью определяется любой совокупностью из й правильно полученных вычетов. Таким образом, из С" способов определения 1(Х) ровно С„ ч способов должны быть согласованы, т.
е. давать правильный многочлен 1(Х). Возможно, что ! — 1 переданных вычетов должны быть изменены так, чтобы они стали вычетами некоторого другого много- члена 1(Х) степени А — 1 или меньше, который определяется Й вЂ” 1 правильно полученными вычетами и одним неправильно полученным вычетом. Имеется Сь ~+~ определителей, которые будут давать тот же самый неправильный ответ. Далее, если и — 1) й — 1+ 1, то число правильных определителей превышает число неправильных, так что полипом 1(Х) может быть правильно восстановлен. Это значит, что если 1 выбрать так, чтобы для рассматриваемого кода выполнялось равенство 21+ 1 =и — й+ 1, то все ! ошибок могут быть исправлены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
