Файл: Теория и техника передачи данных и телеграфия учебник..pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.04.2024
Просмотров: 279
Скачиваний: 1
|
§ 6.5. |
Коды Хэмминга |
|
||
6.51. |
Коды |
Хэмминга |
с dM\m = 3 |
|
|
Кодом Хэмминга называют групповой (п, &)-код, матрица |
|||||
проверок которого имеет r = n — k строк и 2Г —1 столбцов, |
причем |
||||
столбцами Н(„,я ) являются |
все |
различные ненулевые /--разряд |
|||
ные числа в двоичной системе |
счисления от 1 до 2 r — 1 . |
|
|||
Из определения |
ясно, что длина |
кодовой комбинации |
равна |
||
п — 2т — 1, а число информационных элементов k = 2r — r—\. Итак, код Хэмминга полностью определяется числом избыточных эле
ментов в кодовой |
комбинации |
n — k. По виду матрицы |
H ( n , f t ) |
легко определить |
минимальное |
кодовое расстояние кода |
Хэм |
минга. Так как все столбцы матрицы проверок различны, то ми нимальное кодовое расстояние больше двух. Для любого числа г можно указать три столбца матрицы Н( п ,ь) (например, столбцы, соответствующие числам 1, 2, 3), являющиеся линейно-зависи мыми.
Следовательно, у любого кода Хэмминга минимальное кодо вое расстояние равно трем, т. е. код Хэмминга способен исправ лять все однократные ошибки. Полное число вариантов одно
кратных ошибок Cnl |
— n=2n-h—l, |
т. е. равно числу строк таб |
лицы декодирования |
с ненулевыми |
синдромами. Это означает, |
что код Хэмминга является совершенным. На основании опреде ления кодов Хэмминга можно построить следующие коды: (7,4)
при |
г = 3, |
(!5,11) при г = 4, (31,26) при г = 5, |
(63,57) при г = 6, |
(127, |
120) |
при г = 7 и т. д. Путем укорочения |
этих кодов можно |
построить коды Хэмминга любой длины. В силу этого любой групповой код, исправляющий одиночные ошибки, принято на зывать кодом Хэмминга.
Коды Хэмминга обладают важным свойством. Если столбцы
матрицы проверок |
представляют |
собой |
упорядоченную запись |
(га — &)-разрядных |
двоичных чисел, то при однократной ошиб |
||
ке синдром равен |
порядковому |
номеру |
элемента кодовой ком |
бинации, в котором произошла ошибка. Действительно, если вектор ошибки Et содержит единицу лишь в одном разряде, соответствующем ошибочному элементу, то при вычислении
синдрома |
/?,Н^( *) все строки |
матрицы \i[n,k), |
соответствующие |
||||||||
нулям |
в |
Eh |
обращаются |
в нулевые |
последовательности |
и лишь |
|||||
строка |
Н(л. й), соответствующая |
«1» |
в Еь |
определяет вид син |
|||||||
дрома, т. е. порядковый |
|
номер |
элемента |
в двоичной |
записи. |
||||||
Например, если в системе передачи используется |
(7,4)-код |
||||||||||
Хэмминга |
с |
проверочной |
|
матрицей |
|
|
|
|
|||
|
|
|
|
"1 |
1 |
1 |
1 |
0 |
0 |
0" |
|
|
|
|
Н(7,4) = |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
|
|
|
.1 |
0 |
1 |
0 |
1 |
0 |
1_ |
|
и переданная комбинация (1 1 0 1 0 0 1) под воздействием
229
помех трансформируется в комбинацию (1 1 0 0 0 0 1), отли чающуюся от переданной в 4-м разряде, то синдром, вычислен ный в декодирующем устройстве приемника, будет иметь вид Sf=100 . Следовательно, ошибка произошла в 4-м разряде.
Кодирующие и декодирующие устройства для кодов Хэмминга строятся на основе систем проверочных соотношений
матрицы |
проверок. При |
этом в случае |
упорядоченной |
записи |
||||||
столбцов |
Н(Л , k) |
в |
качестве проверочных |
разрядов |
удобно |
вы |
||||
бирать |
разряды |
с |
номерами 2\ где і — 0 , 1 , . . . , |
г — 1, |
так |
как |
||||
в этом |
случае |
каждая строка Н( „,*) однозначно |
выражает |
из |
||||||
быточный |
элемент |
через |
информационные. |
|
|
|
|
|||
Рассмотрим построение кодирующих и декодирующих |
||||||||||
устройств |
кода |
Хэмминга на примере (7,4)-кода. |
В этом |
слу |
||||||
чае 1, 2, |
4-й элементы |
кодовой комбинации удобно |
выбрать |
|||||||
избыточными. Тогда связь между избыточными и информаци онными элементами по матрице Н(7,4> устанавливается сле дующим образом:
а, = а 3 + а 3 -f- а 7 , а-, — а-д-\~ ай -f- а 7 , а 4 = а 5 -f- а 6 -+- а 7 .
Структурная схема кодирующего устройства изображена на рис. 6.6а. Информация из источника параллельным кодом запи сывается в 3, 5, 6 и 7-ю ячейки регистра и одновременно по дается на входы соответствующих сумматоров по модулю 2 для формирования избыточных элементов. Сформированные избы точные элементы записываются в 1, 2 и 4-ю ячейки регистра, после чего вся коловая комбинация выводится из регистра к вы ходу передатчика.
Устройство исправления ошибок изображено на рис. 6.66. Принятая кодовая комбинация записывается в приемный ре гистр, ячейки которого в соответствии с проверочными соотно шениями поданы на входы трех сумматоров (вычислитель син дрома). Вычисление синдрома происходит после того, как вся принятая комбинация записана в приемный регистр. При нали чии ошибки на выходе дешифратора появится сигнал, который запишет «1» в соответствующую ячейку регистра исправления. После вычисления синдрома происходит считывание принятой комбинации из приемного регистра через сумматор исправления. На другой вход сумматора исправления подается содержимое
регистра исправления, причем информация из |
одноименных |
ячеек регистров поступает на входы сумматора |
одновременно. |
На выходе сумматора исправления ошибочно принятый элемент будет инвертирован, т. е. исправлен.
Бели код используется только для обнаружения ошибок, то декодирующее устройство упрощается (рис. б.бв). В этом случае достаточно выходы сумматоров S u S2, S3 подать на схему ИЛИ. Если хотя бы одно проверочное соотношение не удовлетворяется, то на выходе схемы ИЛИ появится сигнал «Ошибка».
Рассмотренные примеры дают представление о принципах по строения кодирующих и декодирующих устройств для кодов
|
а) |
|
Источник |
|
|
|
|
|
|
||
|
|
информдц ии |
|
тт |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rn |
|
|
Выход |
|
|
|
Регистр |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|||
|
Tu |
f |
7 |
7 |
7 |
7 |
|
|
|
|
|
|
|
Приемный |
регис/пр |
Т/. |
|
|
|
|
|||
Вход |
у |
/ |
; |
; |
; |
; |
* |
е |
Выход |
Л' наполите/гю |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
I |
|
|
|
анформааион- |
||
|
|
|
|
|
|
|
ТСумматор |
ных |
разрядов |
||
|
|
|
|
|
|
|
|
\испраіления |
|
||
вычисм/пель |
Ц |
|
5 |
і |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Синдрома |
|
|
|
|
|
|
Регистр |
|
|||
Цешиїрраторь," Ж |
исправления |
|
ТЦ Приемный регистр
Выход
н наноли/пея/о анформацг/оннб/х
раз/>/)&0д°
ВычисрителА^
синдрома
.Хэм-минга. Однако более рациональным является построение ко
дирующих и декодирующих |
устройств |
для этого класса |
кодов |
на базе циклических кодов. |
|
|
|
Оценим эффективность кодов Хэмминга. Вероятность нали |
|||
чия ошибок в комбинации |
на выходе |
декодирующего |
устрой- |
ства |
при исправлении ошибок равна Я, |
|
1 - я |
||||||
Р |
а при |
||||||||
обнаружении |
Я 0 |
|
Р |
' 2 r - |
1 V- |
Выигрыш |
по достоверно |
||
|
2Г |
3 |
|
||||||
|
|
|
|
|
|
|
|
||
сти |
по сравнению |
с простыми |
кодами той же длины составляет |
||||||
|
Я ( > 1 , п) |
0 i _ „ |
, т]0 |
Я ( > 1 , п) |
|
0 r |
, т. е. исправле- |
||
І]И = — |
= 2 |
|
= — |
р——- |
|
= 2 Г - 3 |
|||
|
* о ш и |
|
|
|
|
* о и о |
|
|
|
ние однократных ошибок менее эффективно в реальном кана ле, чем проверка на четность или нечетность, в то время как использование кодов Хэмминга для обнаружения ошибок по зволяет обеспечить любую степень повышения достоверности соответствующим выбором числа избыточных элементов п — k.
|
|
6.5.2. Коды Хэмминга |
с d m m |
= 4 |
|
|
На |
основе |
(п, &)-кода Хэмминга |
с а*М И н = |
3 можно получить |
||
( я + 1 , |
&)-код |
Хэмминга с dMvm = 4. |
Для этого |
в кодовую |
комби |
|
нацию |
ВВОДИТСЯ ДОПОЛНИТеЛЬНЫЙ |
ИЗбыТОЧНЫЙ Элемент, |
Я І В Л Я Ю - |
|||
щийся результатом проверки на четность всех элементов кодо
вой комбинации. Матрица проверок для (п+ |
1, k) -кода |
Хэмминга |
|||||||||||
с я'мип = 4 получается |
из матрицы |
проверок |
(п, &)-кода |
с d„mi |
— 'S |
||||||||
путем введения дополнительной |
строки из /г+1 единиц и прини |
||||||||||||
мает вид |
|
|
|
|
|
|
|
О" |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Н(Л |
|
|
|
н(л, |
к) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
|
|
|
|
|
|
|
|
|
|
11 |
11 |
|
|
|
|
||
где |
Н(„,/4) — матрица |
проверок |
кода |
с |
<іМин = 3. |
Например, |
из-. |
||||||
(7,4)-кода можно получить (8,4)-код |
с а*М ин = 4. Матрица прове |
||||||||||||
рок |
(8,4)-кода |
имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- 1 |
1 |
1 |
1 |
0 |
0 |
0 |
о- |
|
|
|
|
Н(8,4) = |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|
|
||
|
|
|
|
|
|
||||||||
|
|
|
- 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 - |
|
|
|
|
|
§ |
6.6. |
Циклические коды |
|
|
|
||||||
|
6.6.1. |
Определение |
|
циклического |
|
(п, |
к)-кода |
|
|
||||
Среди многообразия групповых кодов особое место занимаютциклические коды, которые отличаются простотой реализации,, возможностью построения кода любой длины с известными кор ректирующими свойствами, рациональным соотношением между7
