Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1151848), страница 113
Текст из файла (страница 113)
Для кодов с малыми значениями к/н более точной является верхняя граница Плоткина: г ~ 2Ы вЂ” 2 — 1ойг(о/). Можно также показать, что существует блочный линейный код (п, /е) с кодовым расстоянием е/, для которого справедливо неравенство 575 9. Радиотехнические системы передачи информации называемое нижней границейВаршамова — Гильберта. Таким образом, границы Хэмминга и Плоткина являются необходимыми условиями существования кода, а граница Варшамова — Гильберта— достаточным.
Эти границы позволяют оценить эффективность блочных кодов и целесообразность их применения, 9.5.2. Линейные блочные коды Линейный (и, lс)-код можно получить из lс линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными. Представим базисные кодовые комбинации в виде (пк7с)-матрицы ьн %2 "' К!» в21 в22 "' 02» в»1 Я»2 "' в»» (9.9) В теории кодирования матрица С называется порождающей.
Тогда процесс кодирования заключается в выполнении операции В=АС, где А — вектор размерности lс, соответствующий сообщению;  — вектор размерности и, соответствующий кодовой комбинации. Таким образом, порождающая матрица (9.9) содержит всю необходимую для кодирования информацию. Она должна храниться в памяти кодиРуклцего устройства.
Для двоичного кода объем памяти равен «кп двоичных символов. При табличном задании кода кодирующее устройство должно запоминать и 2 двоичных символов. Две порождающие матрицы, отличающиеся друг от друга только поРядком расположения столбцов, задают коды, которые имеют одинаковые расстояния Хэмминга между соответстствующнмн кодовыми комбинациями, а следовательно„одинаковые корректирующие способности. Такие коды называются эквивалентными. В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единице среди информационных символов. При этом порождающую матрицу (9.9) удается записать в канонической форме: 576 9.5, Помекоуотойчивое кодирование и декодирование 100...00 ~„,, 010...00 (9.10) где 1 — единичная (Ус к Уг)-подматрица; Р— (к к (77 — lг))-подматрица проверочных символов, определяющая свойства кода.
Матрица (9.10) задает систематический разделимый код. Можно показать, что для любого линейного кода существует эквивалентный систематический код. Линейный (и, к)-код может быть задан так называемой проверочной матрицей Н размерности г к и. При этом некоторая комбинация В принадлежит коду только в том случае, если вектор В ортогонален всем строкам матрицы Н, т. е. если выполняется равенство ВН' =О, (9.1 1) где т — символ транспонирования матрицы. Поскольку равенство (9.11) справедливо для любой кодовой комбинации, то Каноническая форма матрицы Н имеет вид е К ... е 100...00 д2~„2 ...
дц 2 010...00 (9.12) д 000...01 где Р' — подматрица, столбцами которой служат строки подматрицы Р из соотношения (9.10); 1 — единичная (г к 1)-подматрица. Подставляя (9. 12) в (9.11), можно получать п — lг уравнений вида Ь8„9,'~ ЮК,„7Ь1 =О, 5'=1,2, ...,п — 18, (9.13) 577 20 — 78! 6 которые называются уравнениями проверки. Из (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) перепишем в виде а(х)х Ю с(х) = т(х)р(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
