Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 180
Текст из файла (страница 180)
Непрерывные кодзи представляют собой последовательности информационных и проверочных разрядов. Блоковые и непрерывные коды делят на систе.матические и несистематические. К систематическим относят коды, разряды которых можно разделить на проверочные и информационные по их положению в кодовой комбинации. Несистематические коды этим свойством не обладают. По используемым в процессе кодирования математическим операциям различают линейные и нелинейные коды. К ликейнььм по произвольному модулю (см. разд. 28) кодам относят такие, у которых операции кодирования описываются линейными по этому модулю соотношениями. Сумма по модулю нескольких разрешенных комбинаций дает при этом разрешенную комбинацию этого же кода.
Нелинейные коды указанными свойствами не обладают. 24.6. Пннейные блоковые коды 24.6.1. Порождающая матрица кода Обеспечивает линейное преобразование т-мерной т т информационной вектор-строки и в 1-мерную х с добавлением /г = 1 — т проверочных символов, так что х =и 8, х=й н, (24.18) где 8 — порождающая.матрица. Число ц возможных значений элементов матриц й, х, н конечно. Вычисления (24.18) ведутся поэтому в конечных числовых полях Сгг(ц) (полях /алуа, см.
разд. 28.4). При простых значениях числа а они выполняются в арифметике по модулю д, часто по модулю 2 (в двоичных кодах). Матричная запись (24.18) компактно заменяет большую таблицу преобразования символов. Так, преобразование 2'о(более миллиона) двадцатиэлементных дво- 402 ичных кодовых комбинаций в сорокаэлементные описывается порождающей матрицей й размера 20х40. Порождающая матрица систематического кода. Это блочная матрица тх! = тх(т + й), например; 8=]! !]/!]1. (24.19) Включает единичную лгатрицу 1 размера тхл и контрольную /Ь размера тхк .мал~рацу (черта разделяет здесь эти матрицы как блоки матрицы 8).
В расширенном векторе х в (24.19) здесь следуют т информационных вначале и к контрольных символов затем 14.28]. 24.6.2. Проверочная матрица систематического кода Так называют матрицу й размера кх 1, преобразующую принятый 1-мерный код у = х + и, искаженный аддитивной помехой и, в /г-мерный вектор-синдром с=й у, вскрывающий наличие ошибок. Применительно к (24.19) матрица й имеет блочное представление где 1' — единичная матрица размера /гхк. Вектор-синдром с равен нулю в отсутствие ошибок с=йх=нй н=])-Ь ]Г)] н=-Ь н+Ь п=О т т, ! т т Цт и содержит ненулевые элементы при их наличии с = Ь у = Ь(х + и) = и и.
(24 21) Проверочную матрицу и представляют также в виде блочной 1-меркой вектор-строки й = ]] и! йз ... Ь/ ]), состоящей из к-мерных вектор-столбцов. Такие вектор- столбцы заменяют й-разрядными числами /г, и используют это представление для обнаружения и исправления ошибок. Однако для этого элементы матрицы й должны удовлетворять определенным требованиям. Для обнаружения ч ошибок должно быть выполнено условие 2 Ь, м 0 (пюд 2) при любом сочетании ч искаженных символов. Для исправления ошибок сумма ~ Ь, (шод 2) при некотором их сочетании не должна совпадать с аналогичной суммой при другом сочетании.
Например, при исправлении одиночной ошибки уже все столбцы проверочной матрицы должны быть различны. 24.6.3. Простейшие двоичные линейные блоковые коды Коды с повторением. Это низкоскоростные систематические коды с хорошими корректирующими свойствами. Контрольная матрица в систематическом представлении этих кодов (24.19) сводится к блоку единичных матриц Ь = ]] 1 1 ... ! ]]. Коды с проверкой на четность.
Это также систематические коды. В зависимости от числа проверочных символов /г = 1 — т бывают; а) высокоскоростными с невысокими контрольными качествами; б) низкоскоростными с повышенными контрольными качествами. Для первого случая возможно добавление всего одного проверочного символа (к = 1). Контрольная матрица Ь=|] 1 1 ... 1 ]~ составляется из единиц, а контрольный рет зультат сводится к сумме А н по модулю два элементов О, 1 информационного вектора на четиость, т.е. к нулю, если их сумма четная, и к единице, если она нечетная. При /с = 2 проверяются на четность отдельные груп- О О О[1 пы кода.
Так, при с5 = ~ на четность О О О проверяется две трехэлементные комбинации кода и=11 и1 кг из и4 из ио 11, в частности комбинации и1 со из и к4 из иь с выдачей порознь контрольных результатов. 24.6.4. Коды Хзмминга Это коды, исправляющие одиночные ошибки. Согласно разд. 24.5.2, достаточно, чтобы все столбцы проверочной матрицы были при этом различны.
Для числа проверочных символов /! длина кода ! = 2 — 1. Коды Хэмминга в отличие от (24.19) часто систематизируют так, чтобы каждый столбец проверочной матрицы отображал его номер. Так, коду Хэмминга (! = 7, т = 4) определяют проверочную в и порождающую 8 матрицы вида 1 0 1 0 ! 0 1 О 1 ! 0 О 1 1 О О 0 ! ! ! ! (24.22) 1 1 1 0 0 0 О 1 0 0 1 ! 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 В случае искажения одного разряда при декодировании вьщается его номер. Наряду с двоичным кодом (! = 7, т= 4) или (7, 4) для /с = 3 возможны двоичные коды Хэмминга (15, 11) для /с = 4, (31, 26) для /с = 5, (63. 57) для /с = 6, (127, 120) для /с = 7 и т.д.
24.6. Двоичные циклические коды Это разновидность блоковых двоичных кодов. Наименование «циклические» связано с возможностью проведения циклических сдвигов блоковых кодовых комбинаций, т.е. переходов в процессе кодирования и декодирования от комбинаций х,, хь ..., х~ ь х~ ~ к комбинаЦиам хс ь хь —., хс,.
Комбинации представляют также в многочленной (полииомиальной) форме; !-1 /-2 хс и»хс эх + ... +хя+х,=х(х), (24.23) где х — неопределенная переменная (см. разд. 19.9), а х; двоичные (до разд. 24.6.8) цифры О, 1. Как показывается ниже, кодирование и часто декодирование циклических кодов сводятся к своеобразной фильтрации — получению сверток по модулю два, что упрощает аппаратуру [4.7, 4.13). 24.6.1. Техническая реализация, математическое описание и применение циклического сдвига Циклический сдвиг кодовой комбинации хм -1 + хь...,х„„хс, осуществляется простейшим рекур- Рис.
24.3 сивным фильтром (рис. 24.3) в виде регистра сдвига с обратной связью с выхода на вход. Пусть в регистр с числом ячеек ! введены значения хс „х~ ь...,хыхе начиная со старшего разряда. Сдвиг на одну позицию приводит к кодовой комбинации хс и хс 3, ..., хь, хьь Последняя соответствует многочлену хьд(з), равному остатку (см. разд. 28.2) от деления многочлена в х(х) на многочлен х — 1: ! хьд(х) = х х(х) (пюд (х — 1)), (24.24) в чем можно убедиться, проведя операцию деления в двоичной арифметике. Если сдвиг повторяется н раз, то ход(х) = хч х(х) (пзос( (з — 1)) .
(24.25) Повторение сдвига / раз возвращает систему в исходное состояние. Величину ! называют длиной цикла [4.32). Порождающий, проверочный н синдромный многочлены циклического кода. Заменяют порождающую 8 и проверочную и матрицы, а также вектор-синдром ошибок с систематического блокового кода (разд. 24.5). Матричное соотношение (24.21) заменяется скалярным с(х) = /с(в)[х(х) + я(х)) = /с(х) п(х) (шод (х — 1)), (24.26) где с(х), /с(х), х(в), п(з) — синдромный, проверочный, кодовый и помеховый многочлены.
Выражение кодового миогочлена х(х) через информационный и(х) и порождающий 8(х) многочлены заменяет матричное соотношение (24.8): х(з) = и(х) 8(х), (шод (х — 1)). (24.27) Совместимость соотношений (24.26) и (24.27) обеспечивается при условии 8(х) /с(з) = х — 1, (24.27 а) поскольку при этом /с(х) х(х) = и(х) 8(х) /г(х) = 0 (юос( (х — 1)). / И порождающий, и проверочный многочлены явля/ ются согласно (24.27а) делителями двучлена х — !. Признаком отличия разрешенных комбинаций от искаженных является согласно (24.27) делимость их многочленов х(х) на порождающие многочлены 8(х).
24.6.2. Формирование и декодирование несистематических циклических кодов Без дополнительных операций формирования (разд. 24.6.3) циклические коды — несистематические. Реализуется на основе регистров сдвига и сумматоров по модулю два. Запись элементов в ячейки регистра проводят параллельно или последовательно. Примеры соответствующих кодеров (рис. 24.4 и 24.5) относятся к сигнальному и порождающему многочле- 3 нами(х)=изх + + + + + игх + исх + но 1-'ос/11/гСС 2 ас аг и8(з) =х + з + 1 3 2 или 8(х) г в» х + 3 Рис. 24.4 1, Последние можно записать ио В! 1'гССз аг а1 Вм + + + в виде 8(х) = з + Вхох + агх + -ь п1з + 1.
г Рис. 24.5 где а!2 = 1 или О. Получаемый кодовый многочлен (24.27) имеет вид: 3 3 4 х(х) = изх + (огиз+ иг)х + (азиз + агиг + и1)х + 3 2 2 +(из+а1иг+аги! +по)х +(и +а1и1+агио)х ~ + (и! + а1ио)х+ ио. хол 403 Он соответствует матричной записи кода (24.18): 1 42 41 1 0 О 0 1 а2 а1 1 О О 0 1 а2 а! 1 О О О 1 а2 а! ! х =а 8= и! ио Процесс декодирования несистематического кода. При декодировании многочлен у(в) = х(в) + п(в), где п(в) — многочлен ошибок, умножается иа проверочный многочлен Ь(в), удовлетворяющий (24.26). Умножение реализуется аналогично умножению на 8(в).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
