Куприянов А.И. Радиоэлектронная борьба (2013) (1186257), страница 25
Текст из файла (страница 25)
В особенности это ограничение существенно для кодов большой длины. Поэтому к настоящему времени созданы и продолжают разрабатываться коды, не требующие запоминания большого количества комбинаций. Известно много помехоустойчивых кодов, которые классифицируются по различным признакам. Прежде всего корректирующие коды разделяются на два больших класса: блочные и непрерывные. При блочном кодировании последовательность элементарных сообщений источника разбивается на отрезки и каждому отрезку ставится в соответствие определенная последовательность (блок) кодовых символов, иначе называемая кодовой комбинацией.
Множество всех кодовых комбинаций, разрешенных (возможных) при данном способе кодирования, и есть блочный код. Длина блока может быть как постоянной, так и переменной. Соот- необнаруживаемой ошибки в первом приближении можно определить как вероятность одновременного искажения одной единицы и одного нуля: но = ~з ош (~ вш) 4(~ '" ош) = 2Рош (~ ош) (16.9) где Р— вероятность искажения символа. Среди разделимых кодов выделяют коды линейные и нелинейные. К линейным относятся коды, в которых поразрядная сумма по модулю 2 любых двух разрешенных кодовых слов также является разрешенным кодовым словом.
Линейный код называется систематическим, если первые Й символов любой его кодовой комбинации являются информационными, а остальные и — 1 символов — проверочными. Наиболее простой линейный систематический код — это (и, и — 1), содержащий один проверочный символ, который равен сумме по модулю 2 всех информационных символов. Такой код называется кодом с проверкой на четность. Он позволяет обнаружить все сочетания ошибок нечетной кратности.
Вероятность необнаруженной ошибки в первом приближении можно определить как вероятность искажения двух символов: Р„.=С„'Р. (1-Р. )" '. (1б.10) 312 Глава 1б. Помехозащита радиосистем передачи информации 1б.2. Кодирование в помехозащищенных РСПИ 313 Избыточность кода определяется выражением 1оя Ф Х =1- 1г1я Ж~ или для двоичного кода (т=2), когда %=2, а Юо — — 2: П. й р Х=1 — — = —, л и (16.11) (16.12) г> 1оя2 Ы (16.16) др ~/с р / У с„' ' ~с где — называется относительной скоростью кода. П Для оценки степени сходства разных комбинаций, составляющих код, в пространстве кодовых последовательностей вводится метрика, т.
е. опре- деляется правило вычисления расстояния между кодовыми комбинация- ми. Наиболее употребительна метрика, основанная на использовании рас- стояния Хзммиига И(В;, Я.), которое определяется числом разрядов, в которых В; отличается от Вч Для двоичного кода П а~в„в,) = ~ь„о+ь,, (16.13) гр- 1 где Ь и о — символы кодовых комбинаций В и В соответственно; Ю вЂ”вЂ” принимается только в случае, если входной сигнал не попадает в указанную область, в противном случае приемник отказывается от принятия решений и заменяет данный символ специальным символом стирания.
Для восстановления стертых символов используются корректирующие коды. Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния путем введения избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. К сожалению, задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена.
Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных и и Й, которые часто используются для выяснения того, насколько код близок к оптимальному, имеющему минимальное кодовое расстояние для заданной корректирующей способности. Так, для блочного линейного кода (п, й) справедливо неравенство Глава 1б. Помехозащита радиосистем передачи информации 1б.2. Ходирование в помехозащищенных РСПИ 315 314 с~ — 1 И вЂ” 1 ошибки кратности 1> — где, как и прежде, — целая часть 2 2 1 числа . Примером совершенных кодов являются коды Хэмминга 2 По определению, любой линейный код (п, й) можно получить из 1 ли- комбинаций длиной п символов можно расположить по строкам порож- лась в другую), то Я=В*Н =О.
(16.22) дающей матрицы (16.19) С использованием этого обозначения процесс кодирования заключа- ется в выполнении преобразования (16.23) Из определения (16.22) видно, что е — это такая же последовательность из Ж символов, как В и В", но имеющая нули на тех позициях, на которых символы В* не отличаются от символов В и единицы на позициТаким образом, порождающая матрица (16.19) содержит всю необхоях искаженных символов. На основании (16.22) и (16.23) можно утверждимую для кодирования информацию, которая должна храниться в памя- ! (16.22 ут Р нейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях.
Исходные линейно независимые кодовые комбинации называются базисными. Все 1 базисных В=Аб, (16.20) где А — вектор размерности К, соответствующий кодируемому сообщению;  — вектор размерностью и, соответствующий кодовой комбинации. где Б - — вектор размерностью (и — к), называемый синдромом; В* — вектор принятой кодовой комбинации, возможно, искаженной помехами, и поэтому отличающийся от В; Н вЂ” проверочная матрица размерности (» х п), такая, что вектор В принадлежит коду только в том случае, если ВН =0; Т Т вЂ” символ транспонирования матрицы. Если принятая кодовая комбинация В"' совпадает с одной из разрешенных В (либо отсутствуют ошибки в принятых символах, либо из-за действия помех одна разрешенная кодовая комбинация трансформирова- В другом случае Я ~ О, и вцд синдрома зависит только от вектора ошибок е, определяемого как В*= В®е.
Глава 1б. Помехозащита радиосистем передачи информации 316 1б.2. Кодирование в помехозащищенных РСПИ 317 р(х) получается частное С(х). Иначе говоря, кодовая последовательность должна формироваться по правилу В(х) = С(х) р(х), (16.26) причем С(х) в соответствии с (16.26) представляется многочленом сте- пени не выше 1 — 1. Однако при кодировании в соответствии с правилом (16.26) форми- Рис. 16.2. Декодер линейного кода (п, 1с) (16.28) вызывает затруднений. Но для высокоэффективных кодов длиной п»10 разность п — 1 принимает такие значения, что перебор по таблице из 2' ~:; делится на порождающий полином Р(х) нацело (без остатка).
синдромами и векторами ошибок. Такая таблица должна содержать 2 п — И строк. Для каждой принятой кодовой комбинации декодер должен просматривать всю таблицу. При небольших значениях п эта операция не руются только неразделимые коды: информационные и проверочные символы в получаемых кодовых последовательностях оказываются перемешанными. Это свойство затрудняет процесс декодирования. Поэтому на практике чаще всего применяется иной метод нахождения полинома В(х).
Если умножить многочлен С(х) на хи ~ и полученное произведение разделить на р(х), в остатке будет полином г(х): С (х) х' ~ = Ц (х) Р (х) О+ г(х). (16.27) Так как операции суммирования и вычитания по модулю 2 совпадают, из (16.27) следует, что полином 16.2.
Кодирование в помехозащищенных РСПИ 319 Глава 1б. Помехозащита радиосистем передачи информации 318 Работа алгоритма декодирования иллюстрируется схемой рис, 16.4 для кода с порождающим полиномом р(х) =хз Ю х2О+ 1. Такой код имеет кодовое расстояние 0=3 и способен исправлять все однократные ошибки.
од Рис. 16.3. Кодер циклического кода с порождающим полиномом р1х) =хз®л~О+1 От порождающего полинома р(х) зависит корректирующая способность кода, поэтому его выбор очень важен. Степень порождающего многочлена должна быть равна числу проверочных символов. Обнаружение ошибок при использовании циклических кодов сводится к делению много глена В*(х) =В(х)+е(х), соответствующего принятой комбинации, на р(х). Если остаток г(х) оказывается равным нулю, то считается, что ошибки нет, в противном случае фиксируется ошибка. Полипом Рис. 16,4. Декодер циклического кода с порождающим полиномом р(х) = хз Юх2О+1 Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий для ее запоминания и для циклического сдвига, а также на устройство деления на многочлен р(х) для вычисления синд- г(х) = ~В(х)+ е(х)1гпос1 р(х) = е(х) гпос1 р(х) (16,29) зависит только от многочлена ошибок е(х) и играет ту же роль, что и:;,';- Рома В исходном состоянии ключ находится в положении 1.
После семи 1б.2. Кодирование в помехозащищенных РСПИ Глава 1б. Помехозащита радиосистем передачи информации 321 320 строится, например, итеративный код из двух линейных систематических ':- точный код имеет избыточность Х =- 1 — 1с,1'и,. Обозначение такого кода Известно, что для любых целых положительных чисел к и 1<п12 существует двоичный код БЧХ длины п =2~ — 1 с кодовым расстоянием с1> 21+ 1, причем число проверочных символов и — 1с < т1. Относительно более простой является процедура мажоритарного декодирования, применимая для некоторого класса двоичных линейных, в том числе циклических кодов. Основана эта процедура на том свойстве этих кодов, что у них каждый информационный символ можно несколькими способами выразить через другие символы кодовой комбинации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
