Куприянов А.И., Сахаров А.В. Теоретические основы радиоэлектронной борьбы (2007) (1186259), страница 57
Текст из файла (страница 57)
Решение о переданном символе принимается только в случае, если входной сигнал не попадает в указанную область, в противном случае приемник отказывается от принятия решений и заменяет данный символ специальным символом стирания. Для восстановления стертых символов используются корректирующие коды. Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния путем введения избытошости. При этом желательно, чтобы число используемых проверочных символов было минимальным. К сожалению, задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена.
Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных Ф и К которые часто используются для выяснения того, насколько код близок к оптимальному, имеющему минимальное кодовое расстояние для заданной корректирующей способности. Так, для блочного линейного кода (Ю, )е) справедливо неравенство Г> !ОЯ2 „', Сп' (16.16) ю=в ~г(-!1 где г называется верхней границей Хэмминга; ~ ~ означает целую часть е( — ! числа —. 2 Граница Хэмминга (! 6.16) близка к оптимальной для кодов с большими значениями 2У//с.
Для кодов с малыми значениями 2н/к более точной является верхняя граница Плотина: г > 22! — 2 — !оя2 А (16 17) Но существует также блочный линейный код (2н', )е) с кодовым расстоянием А для которого справедливо неравенство д — 2 г<!од2 ~~ С,', ~=0 называемое нижней границей Варшамова — Гильберта.
Границы Хэмминга (16.16) и Плоткина (16.17) являются необходимыми условиями существования кода с параметрами Л', А и е), а граница з!г Глана !б. Помехозои!нта радиосистем передачи ин4ормачии Варшамова — Гильберта †достаточн условием. Равенство в (16.16) справедливо только для так называемых совершенных кодов. Такие коды ( г)-11 исправляют все ошибки кратности и менее и не исправляют ни одной ошибки кратности 1>~ — ~, где, как и прежде, ~ — 2! — целая часть числа —.
Примером совершенных кодов являются коды Хзмминга. 2 По определению, любой линейный код (Л', К) можно получить из К линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными.
Все К базисных комбинаций длиной Л' символов можно расположить по строкам порождающей матрицы П = ~! 6!я ~~. (16. 19) С использованием зтого обозначения процесс кодирования заключается в выполнении преобразования В=Ай, (16. 20) где А — вектор размерности К, соответствующий кодируемому сообщению;  — вектор размерностью Л', соответствующий кодовой комбинации. Таким образом, порождающая матрица (16.19) содержит всю необходимую для кодирования информацию, которая должна храниться в памяти кодируюшего устройства.
Для двоичного кода объем памяти равен КЛг двоичных символов. При табличном задании кода кодирующее устройство должно запоминать Лз! двоичных символов. Копирующее устройство для линейного (Л', К) кода (рис. 16.1) состоит из К-разрядного сдвигающего регистра и «= Л' — К блоков сумматоров по модулю 2. од Рис. !6.!. Кодер линейного (Лг, й) кода Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства через коммутатор. С поступлением 313 16.2. Кодирование в номехозащименных РСПП )г-го информационного символа на выходах блоков сумматоров в соответствии с уравнениями (16.20) формируются проверочные символы, которые затем последовательно поступают на выход кодера. Процесс декодирования сводится к выполнению операции Б= В" Нт, (16.
21) где Я вЂ” вектор размерностью (Ф- )г), называемый синдромом, В* — вектор принятой кодовой комбинации, возможно, искаженной помехами и поэтому отличаюшийся от В; Н вЂ” проверочная матрица размерности (ех рне) такая, что вектор В принадлежит коду только в том случае, если ВН =0; Т вЂ” символ транспонирования матрицы. .
Т Если принятая кодовая комбинация В* совпадает с одной из разрешенных В (либо отсутствуют ошибки в принятых символах, либо из-за действия помех одна разрешенная кодовая комбинапия трансформировалась в другую), то (16. 22) Я=ВнН =О. В другом случае Я в О, и вид синдрома зависит только от вектора ошибок е, определяемого как  — ВЮе. (16. 23) Из определения (16.22) видно, что е — это такая же последовательность из Ф символов. как В и В*, но имеющая нули на тех позициях, на которых символы В* не отличаются от символов В и единицы на позициях искаженных символов. На основании (16.22) и (16.23) можно утверждать, что В=В*И =(В®е)Н =еН, (16.24) где  — вектор переданной кодовой комбинации, а В* — вектор принятой комбинации с возможными ошибками в некоторых символах. Из (16.23) следует, что при 5 = 0 декодер должен принимать решение об отсутствии ошибок, а при Я и 0 — о том, что ошибки лроизо~или.
Число различных синдромов, соответствующих различным сочетаниям ошибок, равно 2д ~ — 1. По конкретному виду синдрома можно в пределах корректируюшей способности кода указать на ошибочные символы, а следовательно, и исправить их. Схема декодера линейного кода (рис. 16 2) содержит К-разрядный сдвигающий регистр, Ф- )е полусумматоров (сумматоров по модулю 2), схемы сравнения, анализатор ошибок и корректор ошибок. На регистре запоминаются информационные символы принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы.
3!4 Гтеа ГД Помехолпигиспсг рпдпосистем передачи ин4ормаиии В результате сравнения формируемых на приемной стороне проверочных символов с принятыми проверочными символами анализатор ошибок определяет ошибочно принятые символы.
Эти решения выносятся на основании анализа синдрома. Исправление информационных символов производится в корректоре. Рпс. 16.2 г2енодер линейного (Гч', lс) подл В общем случае при декодировании линейного года с исправлением ошибок в памяти декодера нужно хранить таблицу соответствий межлу синдромами и векторами ошибок, Такая таблица должна содержать 2 г ~ строк. Для каждой принятой кодовой комбинации декодер должен просматривать всю таблицу, При неболыпих значениях гч' эта операция не вызывает затруднений.
Но для высокоэффективных кодов длиной Ф»10 разность Ф-(с принимает такие значения, что перебор по таблице из 2' " строк оказывается практически невозможным. и-л Пикнические коды относятся к классу линейных систематических. Поэтому для их построения в принципе достаточно знать порождающую матрицу. Но можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинаций полиномами. Так, всякой кодовой комбинации (Ьн, Ьн,, ... Ьо) можег быть поставлено в соответствие число в позиционной двоичной системе, составленное из цифр Ьд н Ьн и ...
Ь„. А значение этого числа определяется полиномом В(х) =Ьм |хд +Ьн зхм +...+ бахо, (16.25) где х — основание системы счисления; Ь я (О, х); суммирование ведется по модулю х. В частности, комбинации двухосновного кода представляются двоичными числами Ь. =О:1, х= 2 и суммирование ведется по модулю 2. Из эквивалентности кодовых комбинаций полиномам (16.25) следует, что все операции при преобразовании кодированных сообщений могут быть представлены как алгебраические действия над полиномами. !62 Коднроианне и помехозомишенных РСПИ 315 Каждый циклический код (ге', !Г) характеризуется порождающим полиномом. Им может быть любой полипом Р(х) степени Ю- К.
который делит без остатка двучлен хл91, а также любую разрешенную кодовую комбинацию В(х). Поэтому процесс кодирования сообщения С(х) сводится к отысканию такого полинома В(х), от'деления которого без остатка на Р(х) получается частное С(х), Иначе говоря, кодовая последовательность должна формироваться по правилу В(х) = С(х)Р(х), (16.26) причем С(х) в соответствии с (16.26) представляется многочленом степени не выше /е-!. Однако при кодировании в соответствии с правилом (!6.26) формируются только неразделимые коды: информационные и проверочные символы в получаемых кодовых последовательностях оказываются перемешанными.
Это свойство затрудняет процесс декодирования. Поэтому на практике чаще всего применяется иной метод нахождения полинома В(х). Если умножить многочлен С(х) на хл-" и полученное произведение разделить на Р(х), в остатке будет полином г(х); С(х)хн "= Ях) Р(х) 9 г(х). (16.27) Так как операции суммирования и вычитания по молулю 2 совпадают, из (16.27) следует, что полином С(х)хм " 9 г(х) = О(х) Р(х) (16.28) делится на порождающий полипом Р(х) нацело (без остатка). Следовательно, этот полипом является разрешенной кодовой последовательностью для кода, заданного порождающим многочленом Р(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
