Калмыков В.В. Радиотехнические системы передачи информации (1990) (1151851), страница 17
Текст из файла (страница 17)
содержащий один проверочный символ, ко- торый равен сумме по модулю 2 всех информационных символов, Этот код, называемый кодом с проверкой на чегносгь, позволяет обнаружить все сочетания ошибок нечетной кратности. Вероят- ность необнаруженной ошибки,.и' первом приближении можно оп- ределить как вероятность искажения двух.бимволов: Рко= С»»Р»«ш(1 — Ры«)" х. Подклассом линейных кодов являются циклические коды.
Они характеризуются тем, что все наборы, образованные циклической перестановкой любой кодовой комбинации, являются также кодо- выми комбинациями. Это свойство позволяет в значительной сте- пени упростить кодирующее и декодирующее устройства, особен- но при обнаружении ошибок и исправлении одиночной ошибки. Примерами циклических кодов являются коды Хэмминга, коды Боуаа — Чоудхури — Хоквингема (Бь!Х вЂ” коды) и др.
Примером нелинейного кода является код Бергера, у которо- то цроверочные символы представляют двоичную запись числа единиц в последовательности информационных символов. Напри- мер, таким является код: 00000; 00101; 01001; 01'110; 10001; 10110; 11010; 11111. Коды Бергера применяются, как правило, в асиммет- ричных каналах. В симметричных каналах они обнаруживают все одиночные ошибки и некоторую часть многократных. Непрерывные коды характеризуются тем, что операции коди- ' рования и декодирования производятся над непрерывной последо- вательностью символов без разбиения ее на блоки. Среди непре- рывных наиболее применимы свергочные коды.
Как известно (см. гл. 3), различают каналы с независимыми и групцирующимися ошибками. Соответственно помехоустойчнвые коды можно разбить па лва класса: исправляющие независимые ошибки и исправляющие пакеты ошибок. Далее будут рассматри- ваться в основном коды, исправляющие независимые ошибки. Это объясняется тем, что хотя для исправления пакетов ошибок раз- работано много эффективных кодов, на практике целесообразнее использовать коды, исправляющие независимые ошибки вместе с устройством перемеження символов или декорреляции ошибок.
Пря Г) этом символы кодовой комбинации не передаются друг за другом, а перемешиваются с символами других кодовых комбинаций. Ес- ли интервал между символами, принадлежащими одной кодовой комбинации, сделать больше чем «память» канала, то ошибки в прелелах кодовой комбинации можно считать независимыми, что и позволяет использовать коды, исправляющие независимые ошибки. 350 7 3 ОСНОВНЫЕ ХАРАКТЕРИСТИКИ И КОРРЕКТИРУЮЩИЕ СВОЙСТВА БЛОЧНЫХ КОДОВ К числу основных характеристик кода относятся длина кода , е основание тп, мощность !у (число разрешенных кодовых комбинаций), полное число кодовых комбинации Мь число и- формационных символов й, число проверочных символов г=п — й, пгс кодовой кмбинации (число единиц в комбинации), избыточность кода, кодовое расстояние.
Из перечисленных характеристик лишь лве последние нуждаются в пояснении. Избыточность кода в общем случае определяется выражением н= 1 — !ОК !У/!ой Л~ь или лля двоичного кола (т=2) при У=2" ь г 7,=1 — — = —, н и где величина й/и называется относительной скоростью кода. Введем понятие кодового расстояния, Предварительно отметим, что для оценки отличия одной коловой комбинации от другой можно использовать расстояние Хзмминга й(Вь В,), определяемое числом разрядов, в которых олна кодовая комбинация отличается от другой. Для двоичного кода й(В;,В)= Х Ь»ЕЬ »=1 тле Ь ь и Ьх — А-е символы кодовых комбинаций В; и В, соотвеггл ьт г»в ее ственно, Ю вЂ” символ суммирования по модулю 2.
Наименыш е расстояние Хэмминга для данного кода называется кодовым расстоянием. В дальнейшем его будем обозначать через й. При независимых ошибках в канале корректирующую способность кола удается выразить через кодовое расстояние. Пусть имеется код с и=1. Учитывая, что искажение одного символа изменяет расстояние Хэмминга на олпу единицу, при применении кода с а=! обнаруживаются пе все одиночные ошибки. Для того чтобы кол мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности 1 требуется код с й,р:1+1.
(7.2) Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, нежели для их обнаружения. Если кратность исправляемых ошибок равна 1, то кодовое расстояние должно удовлетворять условию й>21+1, (7.3) В кзчеетве примерз использовнння грвниц для кодового рзестояния оценим, насколько хорош (близок к оптимзльноыу) БЧХ-.нод (31, 2!) с о==5.
Из верхней грз(нины Хзиыннгз (7.4) находим, что г~9. С другой стороны, нз ннжнен грзннцы Взршзмовн — Гильбертз (7.6) получзем гы!3. Тзкнм образом, ие суШсетвует кодов длинна п=з! с г(=5 и г~9, но еушеетвуют коды длиной и=- =31 е г1 — — 5 н гы!3. Рзосызтрнвземый код имеет г=!б. Очевидно, что он является достаточно хорошим. 7.4.
БЛОЧНЫЕ КОДЫ. ПОСТРОЕНИЕ КОДЕКОВ 7.4.!. ЛИНЕЙНЫЕ КОЛЫ йтт й'тз ° ° йзп 5(зт Узз . ° ° й'зн (7.7) йю Юля ° ° йьн В теории кодирования опа называется порождаюи(ей. Тогда про- ':.':,:';. цесс кодирования заключается в выполнении операции где А — вектор размерностью й, соответствующий сообщению,  — вектор размерностью и, соответствующий кодовой комбинации. Таким образом, порождающая матрица (7.7) содержит всю необходимую для кодирования информацию. Она должна храниться в памяти кодирующего устройства. Для двоичного кода объем памяти равен йХп двоичных символов.
При табличном задании кода кодирующее устройство должно запоминать в.2л двоичных -символов. Две порождающие матрицы, которые отличаются друг от друга только порядком расположения столбцов, задают коды, которые имеют одинаковые расстояния Хэмминга между соответстствующимй кодовыми комбинациями, а следовательно, одинаковые корректирующие способности. Такие коды называются эквивалентныжи. В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единице среди информацион- 354 з Из определения следует, что любой линейный код (а, (г) можно получить из й линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбина-, "„: ции называются базисньгми. Представим базисные кодовые комбинации в виде матрицы размерностью пХА б пых символов.
При этом порождающую матрицу (7.7) удаетса записать в канонической форме 1ОО ..О Од„+,...д,„ О(О...О Од„+,...д,. О=-1)1е Р!! = О О О...О 1д„+,...и„„ , где 1 — единичная АХв подматрица„Р— хХ(п — й) — подматрнца '::, проверочных символов, определяющая свойства кода.
Матрица (7.8) задает систематический код. Можно показать, что для лю- бого линейного кода существует эквивалентный систематический кол. Линейный (и, я) код может быть задан так называемой проверо(гной матрицей Н размерности (гХп). При этом комбинация В принадлежит коду только в том случае, если вектор В ортогопален всем строкам матрицы Н, т. е. если выполняется равенство ГнНт=о, (7.9) ,х( где т †симв транспонирования матрицы. Так как (7.9) справедливо для любой кодовой комбинации, то ОН'=О.
Каноническая форма матрицы Н имеет вид к!з+! Кзь+! Кьз+! 1 О 0 0 0 Н=)(Р', 1)(= й!з+зйяз+я...азь+з 0 1 О...О О кгн йзн ...йь„о О 0...0 1 где Р' — подматрица, столбцами которой служат строки подматрицы Р (7.8), 1 — еднпичная гХг подматрица. Подставляя (7.10) в (7.9), можно получать п — й уравнений ю1да ь Ь„+,гн ~~йг,+,Ь! = О, 1= 1, .... и — й, (7.11) ь-! которые называются уравнениями проверки Из (7.1!) следует, что проверочные символы кодовых комбинаций линейного кода образуются различными линейными комбинациями информационных символов.
Единицы в любой 1-й строке подматрицы Р', входящей и проверочную матрицу (7.10), указывают, какие информационные символы участвуют в формировании )что проверочного символа. Очевидно, что линейный,(п, и) код можно построить, используя уравнения проверки (711).
Прн этом первые А символов кодовой комбинации информационные, а остальные и — )г символов — проверочные, образуемые в соответствии с (7.11). При заданных значениях и н й существует 2аш-"> линейных кодов. Задача заключается в выборе наилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальных линейных кодов не разработаны.
7.4.2. ЦИКЛИЧЕСКИЕ КОДЫ Циклические коды относятся к классу линейных систематических. Поэтому для нх построения в принципе достаточно знать порождающую матрицу. ,Можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинации многочлснами Ь(х) вида Ь (х) Ь вЂ” 1х ВЬ вЂ” тх ЯВ ° ° ВЬ1хВЬО где Ьо сЬя я...Ьс — кодовая комбинация. Над данными мпогочленами можно производить все алгебраические действия с учетом того, что сложение здесь осуществляется по модулю 2. Каждый циклический код (и, и) характеризуется так называемым иорождаюи(им многочленом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
