Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1092038), страница 113
Текст из файла (страница 113)
Из (9.13) следует, что проверочные символы кодовых комбинаций линейного кода образуются различными линейными комбинациями информационных символов. Единицы в любой /-й строке подматрицы Р', входящей в проверочную матрицу (9.12), указывают, какие информационные символы участвуют в формировании 5-го проверочного символа. 9.
Радиотехнические системы передачи информации Очевидно, что линейный (и, lг)-код можно построить, используя уравнения проверки (9.13). При этом первые к символов кодовой комбинации информационные, а остальные и — )г символов — проверочные, образуемые в соответствии с формулой (9.13). С помощью проверочной матрицы сравнительно легко можно построить код с заданным кодовым расстоянием. Это построение основано на следующей теореме: кодовое расстояние линейного (и, Й)-кода равно И тогда н только тогда, когда любые Ы вЂ” 1 столбцов проверочной матрицы этого кода линейно независимы, но некоторые с1 столбцов проверочной матрицы линейно зависимы. Заметим, что строки проверочной матрицы линейно независимые. Поэтому проверочную матрицу можно использовать в качестве порождающей для некоторого другого линейного кода 1п, и — к), называемого двойственным.
Кодирующее устройство для линейного (и, lг)-кода (рис. 9.22) состоит из к-разрядного сдвнгающего регистра и г = и — й блоков сумматоров по модулю 2. Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства через коммутатор К. С поступлением /г-го информационного символа на выходах блоков сумматоров в соответствии с уравнениями (9.13) формируются проверочные символы, которые затем последовательно поступают на выход кодера. Процесс декодирования сводится к выполнению операции 8=ВН', где Я вЂ” вектор размерности и — 1г, называемый синдромом;  — вектор принятой кодовой комбинации. Рис. 9.22.
Структурная схема кодера линейного кода 578 9.5. Помехауатайчивае кодирование и декодирование Если принятая кодовая комбинация В совпадает с одной из разре шенных В (зто имеет место тогда, когда либо ошибки в принятых символах отсутствуют, либо при действии помех одна разрешенная кодовая комбинация переходит в другую), то Б = ВН' = О.
В противном случае Я ~ О, причем внд синдрома зависит только от вектора ошибок е. Действительно, 8 = ВН' = (В 9 е)Н' = еН', где  — вектор, соответствующий передаваемой кодовой комбинации. При Я = О декодер принимает решение об отсутствии ошибок„а при $ Ф О вЂ” о наличии ошибок. Число различных синдромов, соответствующих разным сочетаниям ошибок, равно 2к~е — 1. По конкретному виду синдрома можно в пределах корректирующей способности кода указать на ошибочные символы и исправить их.
Декодер линейного кода (рис. 9.23) состоит из к-разрядного сдвигаю- щего регистра, п — к блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошн- Рне. 9.23. Структурная схема декодера линейного кода 579 20' 9, Радиотехнические системы передачи информации бок по конкретному виду синдрома, получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов, определяет места ошибочных символов.
Исправление информационных символов проводится в корректоре. Заметим, что в общем случае при декодировании линейного кода с исправлением ошибок в памяти декодера должна храниться таблица соответствий между синдромами и векторами ошибок, содержащая 2 строк. С приходом каждой кодовой комбинации декодер должен перебрать всю таблицу.
При небольших значениях и — lс эта операция не вызывает затруднений. Однако для высокоэффективных кодов длиной и, равной нескольким десяткам, разность и — к принимает такие значения, что перебор таблицы из 2"~ строк оказывается практически невозможным. Например, для кода (63, 51), имеющего кодовое расстояние а'= 5, таблица состоит из 2'~ = 4096 строк. При заданных значениях и и 1е существует 2"" ~~ линейных кодов.
Задача заключается в выборе наилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальных линейных кодов не разработаны. Циклические коды относятся к классу линейных систематических. Поэтому для их построения, в принципе, достаточно знать порождающую матрицу. Можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочленами Ь(х) вида Ь(х) = Ь„| х ~ Э Ьч ах 1 9 ... Э Ь1х 9 Ьо, где Ьн 1 = О, 1, ..., и — 1, — символы кодовой комбинации. Над данными многочленами можно проводить все алгебраические действия с учетом того, что сложение здесь осуществляется по модулю 2.
Каждый циклический код (и, к) характеризуется так называемым поролсдающим многочленом. Им может быть любой многочлен р(х) степени п — lе, который делит без остатка двучлен х" чи 1. Циклические коды характеризуются тем, что многочлеиы Ь(х) кодовых комбинаций делятся без остатка нар(х). Поэтому процесс кодирования сводится к нахождению по известным многочленам а(х) и р(х) многочлена Ь(х), делящегося на р(х), где а(х)— многочлен степени к — 1, соответствующий информационной последовательности символов. Очевидно, что в качестве многочлена Ь(х) можно использовать произведение а(х)р(х).
Однако при этом код оказывается несистематическим, что затрудняет процесс декодирования. Поэтому на практике, в основном, применяется следующий метод нахождения миогочлена Ь(х). умножим многочлен а(х) на х х и полученное произведение разделим на р(х). Пусть 580 9.5. Помехоустойчивое кодирование и декодирование а(х)х е = т(х)р(х) Ю с(х), (9.14) где т(х) — частное, а с(х) — остаток.
Поскольку операции суммирования и вычитания по модулю 2 совпадают, то выражение (9.14) перепишем в виде а(х)х Ю с(х) = т(х)р(х). (9.15) Из соотношения (9.15) следует, что многочлен а(х)х Ю с(х) делится нар(х) и, следовательно, является искомым. Многочлен а(х)х имеет следующую структуру: первые л — Iг членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х). Многочлен с(х) имеет степень меньше л — Ф. Таким образом, в найденном много- члене Ь(х) коэффициенты при х в степени л — Ф и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемых многочленом с(х), совпадают с проверочными символами. В соответствии с формулой (9.15) процесс кодирования заключается в умножении многочлена а(х) на х " и нахождении остатка от деления а(х)х'~ нар(х) с последующим его сложением по модулю 2 с многочленом а(х)х" ".
Операции умножения и деления многочленов легко осуществляются линейными цепями на основе сдвигающих регистров 1133). В качестве примера на рис. 9.24, а представлена схема умножения многочлена Ь(х) степени л = б на многочленг(х) = х' Ю х Ю 1 по модулю х" Ю 1. Нетрудно убедиться, что после семи тактов в регистре записывается многочлен Ь(х)Дх) шос1(х' Ю 1).
При делении многочлена Ь(х) степени и = б на многочленДх) = х Ю х Ю! г (рис. 9.24, б) после семи тактов в регистре оказывается записанным остаток от деления. 6 Рнс. 9.24. Схемы умножения (а) н деления (д) многочленов (частный случай) 581 9. Радиотехнические системог передачи информации Вход о 2 Рис. 9.25. Структурная схема кодера циклического кода с порождающим многочленом р(х) = х Ю х 9 1 На основе приведенных схем умножения и деления многочленов строятся кодирующие устройства для циклических кодов.
На рис. 9.25 в качестве примера приведена схема кодера для кода (7, 4) с порождающим многочленомр(х) = х 9х 9 1. В исходном состоянии ключи К1 и Кг нахо- г дятся в положении 1. Информационные символы поступают одновременно на вход канала и на выход ячейки х сдвигающего регистра (это соответствует умножению многочлена а1х) на х ). В течение четырех тактов происходит деление многочлена а(х)х' на многочлен р(х) = х' 9 хг 9 1. В результате в регистре записывается остаток, представляющий собой проверочные символы, Ключи К, и К, перебрасываются в положение 2, и в течение трех последующих тактов содержащиеся в регистре символы поступают в канал. Циклический код может быть задан проверочным многочленом Ь(х): кодовая комбинация В принадлежит данному циклическому коду, если Ь(х)Ь(х) = О щоб (х" 9 1).
Проверочный многочлен связан с порождающим соотношением Ь(х) = (х" 9 1)/р(х). Задание кода проверочным многочленом эквивалентно заданию кода системой проверочных уравнений 19.13). Характерной особенностью циклического кода является то, что все проверочные уравнения можно получить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение.
Например, для кода 17, 4) с порождающим многочленом р(х) = =х' 9 х' 9 1 проверочный многочлен имеет вид Ь(х) =х' 9 х' 9 х 9 1. Проверочные уравнения получаются из условия Ь(х)Ь(х) = О щос1 (х' 9 1) . Осуществив умножение и приравняв коэффициенты при х, х и х нулю, получим следующие уравнения, разрешенные относительно проверочных символов: 582 9.5. Памвхоустойчивов кодирование и декодирование Ьг = Ьв 9 Ь4 9 Ьз Ь| = Ьз 9 Ьз 9 Ьг (9 16) Ь =Ь,9Ь 9Ь. В качестве примера на ег иг рис. 9.26 показана схема кодера циклического кода (7,4), задаваемого проверочным многочле- з 9 г Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
