Учебное пособие разработал



бет12/50
Дата17.05.2020
өлшемі14.65 Mb.
түріУчебное пособие
1   ...   8   9   10   11   12   13   14   15   ...   50

Исправление ошибок. Если вероятность ошибки превышает рош = 10–5, то образуются пакеты ошибок и от их маскирования приходится переходить к исправлению. Для исправления ошибок применяют помехоустойчивое кодирование. При этом наиболее широкое распространение получили блочные линейные (m,k)-ко-ды. У таких кодов передаваемая последовательность символов разделена на блоки, содержащие одинаковое число символов. Общее число символов (битов) в кодовом слове равно m, из них информационными являются первые k символов, а последние r = т – k символов — проверочными. Проверочные символы формируются в результате выполнения некоторых линейных операций над информационными символами. В частности, проверочные символы могут являться суммой по модулю 2 различных сочетаний информационных символов. Чем больше число проверочных символов, тем больше корректирующие возможности кода. Особенностью линейного кода является также то, что сумма (и разность) входящих в код кодовых слов также является кодовым словом, принадлежащим этому коду.

Корректирующие коды характеризуются избыточностью. Она определяется относительным увеличением длины блока из-за введения в него дополнительной проверочной информации и оценивается выражением



(1.39)

где Rизбыточность кода.

Наиболее известной разновидностью блочных линейных (т, k)-кодов являются коды Хэмминга. Для каждого т существует (2m–1, 2m–1 – m)-код Хэмминга. Кроме параметров т и k, важным является минимальное расстояние d, определяющее меру различия двух наиболее похожих кодовых слов. Расстоянием d по Хэммингу между двумя q-ичными последовательностями х и у длины n называется число позиций, в которых они различны. Это расстояние обозначается d(x,y). Например, если х = 10101 и у = 01100, то имеем d(10101, 01100) = 3. При этом минимальное расстояние кода равно наименьшему значению из всех расстояний по Хэммингу между различными парами кодовых слов в коде; (п, k)-код с минимальным расстоянием d называется также (п, k, d)-кoдoм.

Из теории помехоустойчивого кодирования известно, что если произошло t ошибок и расстояние от принятого слова до каждого другого больше t, то декодер исправит эти ошибки, приняв ближайшее к принятому кодовое слово в качестве действительного переданного. Это будет всегда так, если



(1.40)

Например, для обнаружения одиночной ошибки d = 2. Это означает, что достаточно информационные кодовые группы увеличить на один разряд. Для исправления одиночных ошибок каждую кодовую группу необходимо увеличить уже на три разряда. С ростом кратности ошибок объем требуемой дополнительной информации резко возрастает. Так, для числа k битов аудиоданных требуется следующее число контрольных (дополнительных, проверочных) битов r в коде Хэмминга, чтобы ошибка могла быть исправлена:




Биты данных k

1–4

5–11

12–26

27–57

58–120

Контрольные биты r

3

4

5

6

7

Контрольные биты рассчитываются (вычисляются) путем сложений по модулю 2. В них участвуют информационные биты аудиоданных по меньшей мере дважды. Чтобы с большой вероятностью обнаружить ошибку в потоке данных, информационные слова и контрольные слова охватываются совместно в блоки. Эти блоки затем снова рассматриваются как отдельные единицы информации и далее кодируются (блочный код). Иногда удается исправлять конфигурацию из t ошибок даже в том случае, если неравенство (1.40) не выполняется. Однако если d < (2t + 1), то исправление любых t ошибок не может быть гарантировано, так как оно зависит от передаваемого слова и конфигурации из t ошибок, возникших внутри блока.



При кодовом расстоянии d = 3 коды Хэмминга имеют длину т = 2r–1. При двух проверочных символах r = 2 существует код Хэмминга (3,1); при r = 3 — код (7,4); при r = 4код (15,11) и т.д. Коды, для которых d = 3, могут исправлять одиночную ошибку. Для нахождения места этой ошибки необходимо выполнить r проверок, представляющих собой операции суммирования по модулю 2. Технически это реализуется достаточно просто. Например, (7,4)-код Хэмминга можно описать с помощью реализации, приведенной на рис. 1.22, а.



Рис. 1.22 — Кодек для простого (7,4)-кода Хэмминга:



а — кодер; б — декодер

При заданных четырех информационных битах данных (i1, i2, i3, i4) каждое кодовое слово дополняется тремя проверочными битами, задаваемыми равенствами



(1.42)

Знак «+» здесь означает сложение по модулю 2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. Шестнадцать разрешенных кодовых слов (7,4)-кода Хэмминга имеют вид (i1,i2, i3, i4, r1, r2, r3):




i1

i2

i3

i4

r1

r2

r3




i1

i2

i3

i4

r1

r2

r3

0

0

0

0

0

0

0




1

0

0

0

1

0

1

0

0

0

1

0

1

1




1

0

0

1

1

1

0

0

0

1

0

1

1

0




1

0

1

0

0

1

1

0

0

1

1

1

0

1




1

0

1

1

0

0

0

0

1

0

0

1

1

1




1

1

0

0

0

1

0

0

1

0

1

1

0

0




1

1

0

1

0

0

1

0

1

1

0

0

0

1




1

1

1

0

1

0

0

0

1

1

1

0

1

0




1

1

1

1

1

1

1

Пусть при передаче в принятом слове v = (i'1, i'2, i'3, i'4, r'1, r'2, r'3). По изображенному на рис. 1.22, б коду вычисляются биты



(1.44)

Трехбитовая последовательность (s1, s2, s3) называется синдромом. Она зависит только от конфигурации ошибок. Всего имеется восемь возможных синдромов: один для случая отсутствия ошибки и по одному для каждой из семи возможных одиночных ошибок, при этом каждая ошибка имеет только свой единственный синдром. Несложно сконструировать цифровую логику, которая по синдрому локализует соответствующий ошибочный бит. После исправления ошибки проверочные символы опускаются. При наличии двух и более ошибок код будет ошибаться: он предназначен для исправления только одной одиночной ошибки в кодовом слове группы.

При d = 4 коды Хэмминга имеют длину т = 2r1 и записываются соответственно как (4,1); (8,4); (16,11) и т.д. Они получаются из кодов Хэмминга с минимальным расстоянием d = 3 добавлением к каждому кодовому слову [см. (1.43)] одного проверочного символа, равного сумме по модулю 2 всех остальных символов, как информационных, так и проверочных для каждого кодового слова исходного (7,4)-кода Хэмминга.

При выборе кода важно определить мощность кода М, т.е. максимальное число кодовых слов в двоичном коде длиной т (множество двоичных слов длины m) при заданном кодовом расстоянии d. Обычно при d = 3



(1.45)

Следовательно, (3, 1)-код Хэмминга состоит всего лишь из двух кодовых слов. Для увеличения числа кодовых слов необходимо увеличить длину кодового слова: для (7,4)-кода Хэмминга уже имеется 16 кодовых слов. С увеличением m растет сложность декодирования. Коды Хэмминга в силу этой причины целесообразно использовать для исправления одиночных независимых ошибок при небольшом числе возможных информационных символов. В частности, коды Хэмминга используют для передачи трехсимвольных комбинаций, определяющих номер шкалы квантования при кодировании ЗС с применением почти мгновенного компандирования.

Достаточно простой процедурой кодирования и декодирования обладают линейные циклические коды (CRC-коды), где разрешенные кодовые слова формируются из других разрешенных слов циклическим сдвигом символов на один шаг вправо. Цикличность позволяет уменьшить объем памяти устройств, осуществляющих кодирование и исправление ошибок, а возможность записи кодовых слов в виде степенных полиномов сводит процедуры кодирования и декодирования к операциям умножения и деления полиномов, легко реализуемых технически.

Кодовое слово Z – (a0, a1, a2,..., an–1), состоящее из n символов, определяется полиномом Y(x) = a0 + a1x + a2x2 +...+ an1xn1. Среди всех полиномов, соответствующих кодовым словам циклического кода, имеется ненулевой полином наименьшей степени. Он называется порождающим, степень его r = n – k (k — число информационных символов, n — число символов в кодовом слове), а свободный член равен единице. Основная особенность порождающего полинома заключается в том, что он полностью определяет циклический код (все кодовые слова циклического кода) и является делителем всех полиномов, соответствующих кодовым словам циклического кода.

Процесс кодирования при использовании циклического кода состоит в следующем. Полином G(x) степени (k – 1), характеризующий k-разрядное передаваемое информационное кодовое слово, умножается на хr. Полученный полином G(x)xr степени k+r1 делится на порождающий полином F(x). В результате деления образуется остаток q(x) степени не более r – 1. Полином Q(x= = xrG(x) + q(x), делящийся на F(x) без остатка, определяет каждое разрешенное кодовое слово циклического кода. Члены полинома Q(x) со степенью r+1 и выше соответствуют информационным символам, смещенным на r разрядов в результате операции умножения, а остаток q(x) от деления — поверочным символам. Для обнаружения или исправления ошибок в циклическом коде обычно используют операцию деления полинома Q1(x) принятого кодового слова на заранее известный порождающий полином F(x). Если остаток от деления не равен нулю, то принятое кодовое слово считается ошибочным. Место ошибки определяется детектором ошибки в результате сравнения остатка от деления с эталонным полиномом, хранящимся в памяти. Биты избыточности, полученные изложенным выше способом, передаются совместно с первоначальными битами данных.




Достарыңызбен бөлісу:
1   ...   8   9   10   11   12   13   14   15   ...   50


©netref.ru 2019
әкімшілігінің қараңыз

    Басты бет