А.И. Куприянов - Основы защиты информации (1022813), страница 25
Текст из файла (страница 25)
Примером нелинейного кода является код Бергера, у которого : роверочные символы формируются как двоичная запись числа ниц в последовательности информационных символов. Напри' ер, таким является код: 00000; 00101; 01001; 01110; 10001; 11010, :1111. Коды Бергера применяются, как правило, в асимметричых каналах. В симметричных каналах они обнаруживают все оди'. очные ошибки и некоторую часть многократных. Непрерывные коды не разбиваются на блоки. Операции ' одирования и декодирования производятся над непрерывной поседовательностью символов. Самые распространенные и удобные я практического применения среди непрерывных — сверточные ' оды.
К числу основных характеристик кода относятся длина кода и, "го основание и, мощность Ф (число разрешенных кодовых ком:инаций), полное число кодовых комбинаций Фо, число инфорационных символов 1, число проверочных символов г= Ж вЂ” Й, кодовой комбинации (число единиц в комбинации), избы: чность кода и кодовое расстояние. Избыточность кода определя' тся выражением (5.4) 115 114 где Р, — вероятность искажения одного символа. 1оа Ф Х =1- 1~0 Ф~ Й г х=1 — — =-, и л (5.5) (5.б) (5.9) (5.10) г > 2И вЂ” 2 — 1ояф (5.7) 117 или для двоичного кода (т = 2), когда Ф= 2», й где — — относительная скорость кода.
и Для оценки степени сходства разных комбинаций, составляющих код, в пространстве кодовых последовательностей вводится метрика, т.е. определяется правило вычисления расстояния. Наиболее употребительная метрика основана на использовании расстояния Хемминга Н(ВьВ~), которое определяется числом разрядов, где В; отличается от В Для двоичного кода где Ь;» и Ь~» — символы кодовых комбинаций В, и В соответственно; Ю вЂ” символ операции суммирования по модулю 2.
Наименьшее расстояние Хемминга для данного кода называется кодовым расстоянием И. При независимых ошибках в канале через кодовое расстояние удобно выражается корректирующая способность кода. Если код имеет 0 = 1, то две кодовые комбинации отличаются минимум в одном символе. Искажение одного символа сразу трансформирует кодовую комбинацию в друтую разрешенную, т.е. код с Н= 1 не способен корректировать ошибки.
Чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, можно получить, что для обнаружения всех ошибок кратности 1требуется код с расстоянием Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, нежели для их обнаружения. Если кратность исправляемых ошибок равна 1, то кодовое расстояние должно удовлетворять условию Ы> 2(+1. Помимо режима декодирования с обнаружением и исправлением ошибок используется режим с восстановлением предварительно стертых ненадежных символов.
В таких системах решающая схема приемника оперирует с некоторой областью неопределенности. Решение о переданном символе принимается только в случае, если принятый входной сигнал не попадает в указанную область, в противном случае приемник отказывается от принятия 116 ений и заменяет данный символ специальным символом сти. Для восстановления стертых символов используются корирующие коды. ';:-.'Таким образом, задача построения кода с заданной корректи' щей способностью сводится к обеспечению необходимого ко'вого расстояния путем введения избыточности. При этом жела- " но, чтобы число используемых проверочных символов было "Нимальным. К сожалению, задача определения минимального а проверочных символов, необходимых для обеспечения за' .
ного кодового расстояния, в общем виде не решена. Имеется "'шь ряд оценок для максимального кодового расстояния при сированных Фи й, которые часто используются для выяснетого, насколько код близок к оптимальному, имеющему ми' мальное кодовое расстояние для заданной корректирующей " особности. :- Так, для блочного линейного кода (Ф,1) справедливо нера' нство Ь~-11 е г — верхняя граница Хемминга; ~ — ~ — целая часть числа ' — 1 . 2 Граница Хемминга (5.9) близка к оптимальной для кодов с льшими значениями Ф/Й. Для кодов с малыми значениями Ф/Й лее точной является верхняя граница Плоткина: Но существует также блочный линейный код (Ф/с) с кодовым " сстоянием 4 для которого справедливо неравенство а-2 г < 1од2,'~, С„', (5.11) >=О азываемое нижней границей Варшамова — Гильберта.
Границы Хемминга (5.9) и Плоткина (5.10) являются необхоимыми условиями существования кода с параметрами Ф, й и И, а ' аница Варшамова — Гильберта — достаточным условием. Равено в (5.9) справедливо только для так называемых совершенных ~~-П '.одов. Такие коды исправляют все ошибки кратности ~ — ~ и Г~ — 11 менее и не исправляют ни одной ошибки кратности 1> ~ — ~, ~г~' Г ~ — 11 И-1 где, как и прежде, ~ — ~ — целая часть числа †. Примером 2 2 совершенных кодов являются коды Хемминга. По определению, любой линейный код (Ф, й) можно получить из ~с линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными.
Все й базисные комбинации длиной Жсимволов можно расположить по строкам порождающей матрицы а=1!а П. (5.12) С использованием этого обозначения процесс кодирования заключается в выполнении преобразования В=А6, (5.13) где  — вектор размерностью Ф, соответствующий кодовой комбинации; А — вектор размерности й, соответствующий кодируемому сообщению. Таким образом, порождающая матрица (5.13) содержит всю необходимую для кодирования информацию, которая должна храниться в памяти кодирующего устройства.
Для двоичного кода объем памяти равен ~сФдвоичных символов. При табличном задании кода кодирующее устройство должно запоминать Ф2~ двоичных символов. Кодирующее устройство для линейного кода (Ф, Ц (рис. 5.1) состоит из й-разрядного сдвигающего регистра и г= (Ф- й) блоков сумматоров по модулю 2. Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства через коммутатор.
С поступлением ~с-го информационного символа на выходах блоков сумматоров в соответствии с уравнениями формируются провероЧные символы, которые затем последовательно поступают в Рис. 5.1. Кодер линейного (Ф, А) кода 118 ':выход кодера. Процесс декодирования сводится к выполнеоперации 8- В4'Нт (5.14) -' 8 — вектор размерностью (Ф- й), называемый синдромом; В*— ': ор принятой кодовой комбинации, возможно„искаженной 'мехами и поэтому отличающийся от В; Н вЂ” проверочная 'хрипа размерности (гх Ф) такая, что вектор В принадлежит ': у только в том случае, если ВН' = О, где т — символ транс'нирования матрицы. ;:: 'Если принятая кодовая комбинация В~ совпадает с одной из ешенных (либо отсутствуют ошибки в принятых символах, из-за действия помех одна разрешенная кодовая комбинатрансформировалась в другую), то (5.15) 8 =В*Н'=О '::;: В другом случае 8 ~ О и вид синдрома зависит только от вектора ибок е, определяемого как В*=ВВе.
(5,16) -::; Из определения (5.16) видно, что е — это такая же последоваьность из У символов, как В и В', но имеющая нули на тех ': зициях, на которых символы В~ не отличаются от символов В ::единицы на позициях искаженных символов.
На основании (5.15) "'(5.16) можно утверждать, что Б = В*Н' = (В Ю е) Н' = еН', (5,17) ::е В' — вектор принятой комбинации с возможными ошибками ;:::некоторых символах;  — вектор переданной кодовой комбинаи. ;:.;:. Из (5.17) следует, что при 8 = О декодер должен принимать , шение об отсутствии ошибок, а при 8~~ Π— что ошибки про'юшли. Число различных синдромов, соответствующих различ, м сочетаниям ошибок, равно 2~ ~ — 1. По конкретному виду рома можно в пределах корректирующей способности кода зать на ошибочные символы, а следовательно, и.исправить их.
Схема декодера линейного (Ф, А) кода (рис. 5.2) содержит йрядный сдвигающий регистр, (Ф-й) полусумматоров (сумма. ров по модулю 2), схемы сравнения, анализатор и корректор "шибок. На регистре запоминаются информационные символы ': ринятой кодовой последовательности, из которых в блоках сум" аторов формируются проверочные символы. В результате сравнеия формируемых на приемной стороне проверочных символов с ринятыми проверочными символами анализатор ошибок опре' ляет ошибочно принятые символы. Эти решения выносятся на 119 в ЫХОД (5.19) В(х) = С(х)Р(х), (5.21) (5.18) 120 Рис. 5.2. Декодер линейного (Ж, )с) кода основании анализа синдрома. Исправление информационных символов производится в корректоре.
В общем случае при декодировании линейного кода с исправлением ошибок в памяти декодера нужно хранить таблицу соответствий между синдромами и векторами ошибок. Такая таблица должна содержать 2~ ~ строк. Для каждой принятой кодовой комбинации декодер должен просматривать всю таблицу. При небольших значениях дуэта операция не вызывает затруднений. Но для высокоэффективных кодов длиной Ф:ь10 разность (Ф-й) принимает такие значения, что перебор по таблице из 2"' ~ строк оказывается практически невозможным, Циклические коды относятся к классу линейных систематических.
Поэтому для их построения достаточно знать порождающую матрицу. Но можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинаций полиномами. Так, всякой кодовой комбинации (Ь~ „Ь„2, ..., Ь0) может быть поставлено в соответствие число в позиционной двоичной системе, составленное из цифр Ь„„Ь„,, ....Ь0. А значение этого числа определяется полиномом В(х) Ь~~~-1х~ + Ь~ 2х~ 2+ ... + Ь х0, где х — основание системы счисления; Ье (О,х); суммирование ведется по модулю х. В частности, комбинации двухосновного кода представляются двоичными числами Ь = 0;1, х= 2, и суммирование ведется по модулю 2. Из эквивалентности кодовых комбинаций полиномам (5.18) следует, что все операции при преобразовании кодированных сообщений могут быть представлены как алгебраические действия над полиномами, : Каждый циклический код (Ф, й) характеризуется порождающим ' иномом.
Им может быть любой полином Р(х) степени (Ф-й), '. рый делит без остатка двучлен х"Ю1, а также любую разре"нную кодовую комбинацию В(х). Поэтому процесс кодирова."я сообщения С(х) сводится к отысканию такого полинома В(х), ':::-деления которого без остатка на Р(х) получается частное С(х). ' аче говоря, кодовая последовательность должна формировать- " по правилу ' ичем С(х) в соответствии с (5.19) представляется многочленом -: пени не выше  — 1. :.'; Однако при кодировании в соответствии с правилом (5.19) ', рмируются только неразделимые коды: информационные и прочные символы в получаемых кодовых последовательностях окааются перемешанными. Это свойство затрудняет процесс деирования, поэтому на практике чаще всего применяется иной етод нахождения полинома В(х).
'!: Если умножить многочлен С(х) на х" ~ и полученное произвение разделить на Р(х), в остатке будет полином г(х): С(х)х" " = 0(х) Р(х) В г(х). (5.20) ':": Так как операции суммирования и вычитания по модулю 2 ' впадают, из (5.20) следует, что полином 'елится на порождающий полином Р(х) нацело (без остатка). Слеовательно, этот полином является разрешенной кодовой послеовательностью для кода, заданного порождающим многочленом , х). ;;:- У полинома С(х) х~' ~ коэффициенты при ~с старших членах со'падают с коэффициентами С(х), а коэффициенты при (Ф вЂ” й) 'авны нулю, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
