Куприянов А.И., Сахаров А.В. Радиоэлектронные системы в информационном конфликте (2003) (1186258), страница 74
Текст из файла (страница 74)
Самые распространенные и удобные лля практического применения орели непрерывных — сверточные коды. К числу основных характеристик кода относятся длина кола л, его основание»н, мошность Л'(число разрешенных кодовых комбинаций), полное число кодовых комбинаций !ув, число информационных символов А, число проверочных символов г= л — )», вес коловой комбинации (число единиц в комбинации), избыточность кода и кодовое расстояние. Избыточность кода определяется выражением (ОК Ф Х=1- 1ов ЛГО (19.11) ( 19.13) гле Ь,» и Ь» — символы кодовых комбинаций В, и В, соответственно; ®вЂ” символ суммирования по молулю 2. Наименьшее расстояние Хэмминга лля данного кода называется кодовым расстоянием д.
При независимых ошибках в канале через коловое расстояние удобно выражается корректируюшая способность кола. Если код имеет гг'= 1, это значит, лве коловые комбинации отличаются минимум в одном символе. Искажение одного символа сразу трансформирует кодовую комбинацию в другую разрешенную, т.е. кол с гг'= 1 не способен корректировать ошибки. Чтобы код мог обнаруживать любую одиночную или лля двоичного кода (гп = 2), когда Л!= 2, а Л~в = 2" А г х=(- — = —, (19.12) /с п и гле — называется относительной скоростью кола. Для оценки степени сходства разных комбинаций, составляющих код, в пространстве кодовых последовательностей вводится метрика, т.е.
опрелеляется правило вычисления расстояния. Наиболее употре- бительна метрика, основанная на использовании расстояния Хеммин- га В(В„В). Эта величина определяется числом разрялов, в которых В, отличается от Вг Для двоичного кода в В(В„В) =Хб» ®Ь, »м Глава !9. Помехозащита радиосистем передачи информация 460 ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, можно получить, что для обнаруже- ния всех ошибок кратности /требуется код с расстоянием г/ >/+/. (19.14) Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, нежели для их обнаружения.
Если кратность исправляемых ошибок равна /, то кодовое расстояние должно удовлетворять условию Ив 2/-~/. (19.15) У1 г> )од, (19. 16) ! с~-1~ — ~ означает целу 2 где г называется верхней границей Хемминга; ю г/ — ! часть числа —. 2 Помимо режима декодирования с обнаружением и исправлением ошибок используется режим с восстановлением предварительно стертых ненадежных символов. В таких системах решающая схема приемника формирует некоторую область неопределенности. Решение о переданном символе принимается только в случае, если входной сигнал не попадает в указанную область. В противном случае приемник отказывается от принятия решений и заменяет данный символ специальным символом стирания. Для восстановления стертых символов используются корректирующие колы.
Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния за счет введения избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. К сожалению, задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, в общем виде не решена.
Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных п и /г. Полобные оценки используются для выяснения того, насколько код близок к оптимальному, имеющему минимальное кодовое расстояние для заданной корректирующей способности. Так, для блочного линейного кода (и, /г) справедливо неравенство !9.2. Кодирование в помехозашншснных системах перелвчн ннформацнн 461 Граница Хэмминга (19.16) близка к огпимальной для кодов с большими значениями лЯ.
Для кодов с малыми значениями и/)г более точной является верхняя граница Плотина: г > 2гг'- 2 — 1о8зп'. (19.17) Но существует также блочный линейный кол (л, (г) с кодовым расстоянием г(, для которого справедливо неравенство г < )обз ~С,'„ (19.!8) зе называемое нижней границей Варшамова — Гильберта. Границы Хэмминга (19.16) и Плоткина (19.17) являкпся необходимыми условиями существования кода с параметрами и, )г и г/, а граница Варшамова — Гильберта — достаточным условием. Равенство в (19.16) справедливо только для так называемых совершенных кодов. Такие коды исправляют все ошибки кратности ~ — ! и менее и не ис- 2 правляют ни одной ошибки кратности l >~ — ~ где, как и прежле, ! 2 с~ — 11 гг — 1 2 — ~ — целая часть числа —.
Примером совершенных кодов явля- 2 ются коды Хэмминга. По определению, любой линейный код (л, (г) можно получить из Й линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными. Все (г базисные комбинации длиной и символов можно расположить по строкам порождающей матрицы б=!1Ы (19. 19) С использованием этого обозначения процесс кодирования заключается в выполнении преобразования В=А6, (19.20) где А — вектор размерностью (г, соответствующий кодируемому сообщению;  — вектор размерностью и, соответствующий кодовой комбинации. Таким образом, порождающая матрица (19.19) содержит всю необходимую для кодирования информацию, которая должна храниться в памяти кодируюшего устройства.
Для лвоичного кода объем памяти равен (гл двоичных символов. При табличном заланнн кода кодируюшее устройство должно запоминать л 2» двоичных символов. 462 Глава 19. Помехозащита радиосистем передачи ннформаннн Кодируюшее устрой- ство для линейного (и, (с) Вход кода (рис.
19.1) состоит из (г-разрядного сдвигаюшего регистра и г= и — А блоков Ю З Э сумматоров по модулю 2. Информационные сим- волы одновременно постуРнс.!9.!. Кодер линейного (и, Ц кодо пают на вход регистра 1 на выход кодируюшего устройства через коммутатор. С поступлением (г-го информационного символа на выхолах блоков сумматоров в соответствии с уравнениями (19.20) формируются проверочные символы, которые затем последовательно поступают на ныход кодера.
Процесс декодировании сводится к выполнению операции Б=В*Н', (19.21) где Ю вЂ” вектор размерностью (и — (г), называемый синдромом, В*— вектор принятой коловой комбинации, возможно, искаженной помехами и поэтому отличаюшийся от В; Н вЂ” проверочная матрица размерности (гх и) такая. что вектор В принадлежит коду только в том случае, если ВН'=0; т — символ транспонирования матрицы. Если принятая кодовая комбинация В* совпадает с одной из разрешенных В (либо отсутствуют ошибки в принятых символах, либо изза действия помех одна разрешенная кодовая комбинация трансформировалась другую), то 5= В*Н"=О. (19.22) В другом случае Юе 0 и вид синдрома зависит только от вектора ошибок е, определяемого как В* = Вее.
(19.23) Из определения (19.22) видно, что е — это такая же последовательность из и символов, как В и В*, но имеюшая нули на тех позициях, на которых символы В* нс отличаются от символов В и единицы на позициях искаженных символов. На основании (19.22) и (19.23) можно утверждать, что 5= В*Н'= (Ве е)Н = еН', (!9.24) где  — вектор переданной кодовой комбинации, а В* — вектор принятой комбинации с возможными ошибками в некоторых символов.
19.2. Кодирование в помехозагцншенных системах передачи информации 463 Из (19.24) слелует, что при Я = О декодер должен принимать решение об отсутствии ошибок, а при Юн Π— о том, что ошибки произошли. Число различных синлромов. соответствующих различным сочетаниям ошибок, равно 2" ~ — 1. По конкретному виду синдрома можно в пределах корректирующей способности кода указать на ошибочныс символы, а следовательно, и исправить их. Схема декодера линейного кода (рнс. 19.2) содержит )с-разрядный сдвигающий регистр, л — (с полусумматоров (сумматоров по модулю 2). схемы сравнения, анализатор ошибок и корректор ошибок. На регистре запоминаются информационные символы принятой кодовой послеловательности, из которых в блоках сумматоров формируются проверочные символы. В результате сравнения формируемых на приемной стороне проверочных символов с принятыми проверочными символами анализатор ошибок опрелслнсг ошибочно принятые символы. Э~и решения выносятся на основании анализа синдрома.
Исправление информационных символов производится в корректоре. од Рос, И2. Декодер лонедоого (и, lг) кода В общем случае при декодировании линейного года с исправлением ошибок в памяти декодера нужно хранить таблицу соответствий между синдромами и векторами ошибок. Такая таблица должна содержать 2" ~ строк. Для каждой принятой коловой комбинации декодер должен просматривать всю таблицу. При небольших значениях л эта операция не вызывает затруднений.
Но для высокоэффективных колов ллиной л» 1О разность п — (с принимает такие значения, что перебор по таблице из 2" " строк оказывается практически невозможным. Пиклические колы относятся к классу линейных систематических Поэтому лля их построения в принципе достаточно знать порожлаю- 464 Глава !9. Помехоэашита радиосистем передачи информации шую матрицу. Но можно указать лругой способ построения циклических кодов, основанный на представлении кодовых комбинаций полиномами. Так, всякой кодовой комбинации (Ь„п Ь„н ...
Ьв) может быть поставлено в соответствие число в позиционной двоичной системе, составленное из цифр Ь„и Ь„,,....Ьв. А значение этого числа опрелеляется полиномом В(х) = Ь,,х" '+ Ь „т" -'«-...ч- Ь„х', (!9.25) гле х — основание системы счисления; Ь а [О,.х); суммирование ведется по молулю х. В частности, комбинации двухосновного кода прелставляются двоичными числами 6=О; 1, х= 2 и суммирование ведется по молулю 2. Из эквивалентности кодовых комбинаций полиномам (19.25) следует, что все операции при преобразовании копированных сообшений могут быть представлены как алгебраические действия нал полиномами.
Каждый циклический кол (л, гг) характеризуется порожлаюшим полиномом. Им может быть любой полипом р(х) степени л — !г, который делит без остатка лвучлен х" Ю 1, а также любую разрешенную коловую комбинацию В(х). Поэтому процесс кодирования сообшения С(х) сводится к отысканию такого полинома В(х), от деления которого без остатка на р(х) получается частное С(т).
Иначе говоря, кодовая последовательность должна формироваться по правилу В(х) = С(х)р(х), (19.26) причем С(х) в соответствии с (19.26) представляется многочленом степени не выше (г — 1. Однако при копировании в соответствии с правилом (19.26) формируются только неразделимыс коды: информационные и проверочные символы в получаемых кодовых последовательностях оказываются перемешанными. Это свойство затрудняет процесс декодирования. Поэтому на практике чаше всего применяется иной метол нахожления полинома В(х). Если умножить многочлен С(х) на х" ' и полученное произведение разделить на р(х), в остатке будет полипом г(х): С(х)х' г= фх)р(х) а (г(х).
(19. 27) Так как операции суммирования и вычитания по модулю 2 совпадают, из (19.26) слелует, что полипом (19.28) С(х)х" 'Юг(х) = Фх)Р(х) делится на порождаюший полипом р(.т) нацело (без остатка). 19.2. Колнрованнс в помехозвшншенных системах передачи информации 465 Следовательно, этот полипом является разрешенной кодовой последовательностью для кода, заданного порождающим многочленом р(х). У полинома С(х)х коэффициенты при !г старших членах совпадают с коэффициентами С(х), а коэффициенты прн и — «равны нулю, т.е, совокупность п коэффициентов это число, равное передаваемому сообшению, увеличенное на и — В порядков.
Остаток от деления г(х) имеет степень не выше п — гг. Таким образом, коэффициенты при В старших членах полинома С(х)л ке г(х) — это информационные символы, совпадаюшие с символами кодируемого сообшения, а при и — (г младших — проверочные символы. Эти свойства полиномов подсказывают схемотехнические приемы построения кодеров циклического кода. Для примера на рис.!9.3 приведена схема кодера для кода с порождаюшнм многочленом р(х) = хзшхзЮ!. Триггеры Тп Тз и Тз образуют регистр сдвига. В исходном состоянии ключи К! и К2 находятся в положении!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
