Исследование помехоустойчивых кодов (1151931), страница 2
Текст из файла (страница 2)
Такие коды называются эквивалентными.В качестве базисных комбинаций часто выбирают кодовые комбинации,содержащие по одной единице среди информационных символов. При этом порождающуюматрицу (9.9) удается записать в канонической форме:100...00 g1k 1 010...00 g2 k 1G I, P ...... 000...01 g kk 1g1n ... g 2 n ,... ...
... g kn ...(9.10)где I — единичная (k × k)-подматрица; P — (k × (п – k))-подматрица проверочныхсимволов, определяющая свойства кода. Матрица (9.10) задает систематическийразделимый код. Можно показать, что для любого линейного кода существуетэквивалентный систематический код.Линейный (n, k)-код может быть задан так называемой проверочной матрицей Нразмерности r × п. При этом некоторая комбинация В принадлежит коду только в томслучае, если вектор В ортогонален всем строкам матрицы Н, т.
е. если выполняетсяравенствоBHт = 0,(9.11)где т — символ транспонирования матрицы.Поскольку равенство (9.11) справедливо для любой кодовой комбинации, тоGHт = 0.Каноническая форма матрицы Н имеет вид g1k 1gтH P , I 1k 2 ... g1ng 2 k 1 ... g kk 1 100...00 g 2 k 2 ... g kk 2 010...00 ,............ g 2 n ... g kn 000...01(9.12)где Рт — подматрица, столбцами которой служат строки подматрицы Р изсоотношения (9.10); I — единичная (r × r)-подматрица.Подставляя (9.12) в (9.11), можно получать п – k уравнений видаkbk j gi k j bi 0,j 1, 2, K , n k ,(9.13)i 1которые называются уравнениями проверки. Из (9.13) следует, что проверочныесимволы кодовых комбинаций линейного кода образуются различными линейнымикомбинациями информационных символов.
Единицы в любой j-й строке подматрицы Рт,входящей в проверочную матрицу (9.12), указывают, какие информационные символыучаствуютвформированииj-го проверочного символа.Очевидно, что линейный (n, k)-код можно построить, используя уравнения проверки(9.13).
При этом первые k символов кодовой комбинации информационные, а остальные п– k символов — проверочные, образуемые в соответствии с формулой (9.13).С помощью проверочной матрицы сравнительно легко можно построить код сзаданным кодовым расстоянием. Это построение основано на следующей теореме: кодовоерасстояние линейного (n, k)-кода равно d тогда и только тогда, когда любые d – 1 столбцовпроверочной матрицы этого кода линейно независимы, но некоторые d столбцовпроверочной матрицы линейно зависимы.Заметим, что строки проверочной матрицы линейно независимые. Поэтомупроверочную матрицу можно использовать в качестве порождающей для некоторого другоголинейного кода (п, п – k), называемого двойственным.TkT2Б локс ум м ато р о впо m od 2Б локс ум м ато р о впо m od 2T1KВ ы хо дВ хо дБ локс ум м ато р о впо m od 2bk + 1bk + 2bnРис. 1.Структурная схема кодера линейного кодаКодирующее устройство для линейного (п, k)-кода (рис.
9.22) состоит из kразрядного сдвигающего регистра и r = n – k блоков сумматоров по модулю 2.Информационные символы одновременно поступают на вход регистра и на выходкодирующего устройства через коммутатор К. С поступлением k-го информационногосимвола на выходах блоков сумматоров в соответствии с уравнениями (9.13) формируютсяпроверочные символы, которые затем последовательно поступают на выход кодера.Процесс декодирования сводится к выполнению операции% т,S BHгде S — вектор размерности n – k, называемый синдромом; B% — вектор принятойкодовой комбинации.Если принятая кодовая комбинация B% совпадает с одной из разрешенных В (этоимеет место тогда, когда либо ошибки в принятых символах отсутствуют, либо придействии помех одна разрешенная кодовая комбинация переходит в другую), то% т 0.S BHВ противном случае S ≠ 0, причем вид синдрома зависит только от вектора ошибоке.
Действительно,% т (B e)H т eH т ,S BHгде В — вектор, соответствующий передаваемой кодовой комбинации. При S = 0декодер принимает решение об отсутствии ошибок, а при S ≠ 0 — о наличии ошибок. Числоразличных синдромов, соответствующих разным сочетаниям ошибок, равно 2n–k – 1. Поконкретному виду синдрома можно в пределах корректирующей способности кода указатьна ошибочные символы и исправить их.Декодер линейного кода (рис.
9.23) состоит из k-разрядного сдвигающего регистра,n – k блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора.Регистр служит для запоминания информационных символов принятой кодовойпоследовательности, из которых в блоках сумматоров формируются проверочные символы.Анализатор ошибок по конкретному виду синдрома, получаемого в результате сравненияформируемых на приемной стороне и принятых проверочных символов, определяет местаошибочных символов.
Исправление информационных символов проводится в корректоре.Заметим,TkT2T1KчтовобщемВ хо дслучаепридекодированиилинейного кода сисправлением~iаБ локБ локБ локошибок в памятиК о р р е к то рс ум м ато р о вс ум м ато р о вс ум м ато р о вош ибокдекодера должнапо m od 2по m od 2по m od 2храниться таблицасоответствийs1m2междуs2Ан ал и за то рсиндромамииош ибокm2векторамиsrошибок,m2содержащая 2n–kстрок.
С приходомС хем а ср а в н ен и якаждой кодовойРис. 2. Структурная схема декодера линейного кодакомбинациидекодер долженперебрать всю таблицу. При небольших значениях п – k эта операция не вызываетзатруднений. Однако для высокоэффективных кодов длиной п, равной нескольким десяткам,разность п – k принимает такие значения, что перебор таблицы из 2n–k строк оказываетсяпрактически невозможным. Например, для кода (63, 51), имеющего кодовое расстояние d = 5,таблица состоит из 212 = 4096 строк.
При заданных значениях п и k существует 2k(n–k)линейных кодов. Задача заключается в выборе наилучшего (с позиции того или иногокритерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальныхлинейных кодов не разработаны.3. Линейные циклические блочные кодыЦиклические коды относятся к классу линейных систематических. Поэтому для ихпостроения, в принципе, достаточно знать порождающую матрицу.Можно указать другой способ построения циклических кодов, основанный напредставлении кодовых комбинаций многочленами b(х) видаb(x) = bn–1 xn–1 bn–2 xn–2 … b1 x b0,где bi, i = 0, 1, …, n – 1, — символы кодовой комбинации.
Над даннымимногочленами можно проводить все алгебраические действия с учетом того, что сложениездесь осуществляется по модулю 2.Каждый циклический код (п, k) характеризуется так называемым порождающиммногочленом. Им может быть любой многочлен р(х) степени п – k, который делит безостатка двучлен xn 1. Циклические коды характеризуются тем, что многочлены b(х)кодовых комбинаций делятся без остатка на р(х). Поэтому процесс кодирования сводится кнахождению по известным многочленам а(х) и р(х) многочлена b(х), делящегося на р(х), гдеа(x) — многочлен степени k – 1, соответствующий информационной последовательностисимволов.Очевидно, что в качестве многочлена b(х) можно использовать произведениеа(х)р(х). Однако при этом код оказывается несистематическим, что затрудняет процессдекодирования.
Поэтому на практике, в основном, применяется следующий методнахождения многочлена b(х).Умножим многочлен а(х) на xn–k и полученное произведение разделим на р(х). Пустьa(x)xn–k = m(x)p(x) c(x),(9.14)где т(х) — частное, а с(х) — остаток. Поскольку операции суммирования ивычитания по модулю 2 совпадают, то выражение (9.14) перепишем в видеa(x)xn–k c(x) = m(x)p(x).(9.15)Из соотношения (9.15) следует, что многочлен a(x)xn–k c(x) делится на р(х) и,следовательно, является искомым.Многочлен a(x)xn–k имеет следующую структуру: первые п – k членов низшегопорядка равны нулю, а коэффициенты остальных совпадают с соответствующимикоэффициентами информационного многочлена а(х).
Многочлен с(х) имеет степеньменьше п – k. Таким образом, в найденном многочлене b(х) коэффициенты при х в степенип – k и выше совпадают с информационными символами, а коэффициенты при остальныхчленах, определяемых многочленом с(х), совпадают с проверочными символами.В соответствии с формулой (9.15) процесс кодирования заключается в умножениимногочлена а(х) на xn–k и нахождении остатка от деления a(x)xn–k на р(х) с последующим егосложением по модулю 2 с многочленом a(x)xn–k.Операции умножения и деления многочленов легко осуществляются линейнымицепями на основе сдвигающих регистров [133]. В качестве примера на рис. 9.24, апредставлена схема умножения многочлена b(х) степени п = 6 на многочлен f(x) = x3 x 1 по модулю x7 1. Нетрудно убедиться, что после семи тактов в регистре записываетсямногочлен b(x) f (x) mod(x7 1). При делении многочлена b(х) степени п = 6 на многочленf (x) = x3 x2 1В хо д(рис. 9.24, б)К1послесеми1T1T2m2T3m2тактов в регистре2В ы хо доказываетсязаписаннымК21остатокот2деления.Рис.
3. Структурная схема кодера циклического кода с порождающимНа основемногочленом р(х) = x3 x2 1приведенныхсхем умноженияи деления многочленов строятся кодирующие устройства для циклических кодов. На рис.9.25 в качестве примера приведена схема кодера для кода (7, 4) с порождающиммногочленом p(x) = x3 x2 1. В исходном состоянии ключи K1 и К2 находятся вположении 1. Информационные символы поступают одновременно на вход канала и навыход ячейки х3 сдвигающего регистра (это соответствует умножению многочлена а(х) нах3). В течение четырех тактов происходит деление многочлена а(х)х3 на многочлен р(х) = x3 x2 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
