<< Предыдущая

стр. 25
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

женная ошибка.


Сфера декодирования V]



Случай I: Распознаваемая
и исправляемая ошибка




Случай 2: Распознаваемая
ошибка




Случай 3: Необнаруженная I V2
ошибка




Г}= V 3



•Рис. 2.5. Векторное пространство с кодовыми словами «о»
и принятыми словами « X ».

Из рисунка ясно, что корректирующая способность кода зависит
от расстояния между кодовыми словами. Так как мы имеем дело с
двоичными векторами и расстояние между ними определяется чис-
лом несовпадающих компонент, можно записать
п-1
(2.20)
(=0
2-4- Свойства линейных блоковых кодов

Расстояние, измеренное таким образом, называется расстоянием
Хэмминга. Его также можно определить как число отличных от
нуля компонент (вес Хэмминга) скалярной суммы векторов v; и Vj

d(v ii v i )=w«(v i ®vj). (2.21)

Пример: Синдромное декодирование (7,4)-кода Хэмминга.

В качестве примера найдем расстояние Хэмминга между кодовы-
ми векторами vi = (1101000) и v 2 = (0110100) из таблицы 2.1.
Согласно (2.20) имеем

d(vbv2) = (1©0) + (1ф1) + (0©1) + ( 1 ф 1 ) + (2.22)
+ (0 ф 1) + (0 ф 0) + (0 ф 0) = 3

и, с другой стороны, определяя расстояние Хэмминга как (2.21), по-
лучаем
d(v!,v 2 ) = шнЫ © v 2 ) = w[(1010100)] = 3. (2.23)

Важнейшим параметром, определяющим корректирующую спо-
собность кода, является минимальное кодовое расстояние d m i n . Для
его определения мы должны вычислить расстояние Хэмминга меж-
ду всеми парами слов и найти наименьшее. В случае линейных ко-
дов вычисления можно существенно сократить. Используем для этой
цели основное свойство линейных кодов - свойство «замкнутости»
векторного кодового пространства. Это свойство следует непосред-
ственно из определения линейных кодов и формулируется следую-
щим образом: любая линейная комбинация кодовых слов являет-
ся кодовым словом. Рассмотрим множество двоичных кодовых слов
{vo, v i , . . . , v 2 *_i}, образующих код С. Сложим каждое слово этого
множества по модулю два с некоторым зафиксированным произволь-
ным кодовым словом Vj. Тогда множество кодовых слов отобразится
само в себя, а вектор v, перейдет в нулевое кодовое слово. Так как
при таком отображении попарные расстояния кодовых слов не изме-
нятся, а вектор Vj выбран произвольно, то d m i n определяется как

d m i n = min wtf(v), (2.24)
veC\{0}
т.е минимальное кодовое расстояние d m i n линейного кода равно ми-
нимальному весу ненулевого кодового слова.2
2
Из линейности кода также следует симметричность распределения кодовых рас-
стояний относительно любого кодового вектора Прим. перев.
Глава 2. Линейные блоковые коды


Из таблицы 2.1 следует, что dm\n (7,4)-кода Хэмминга равно 3.
Обобщая все приведенные выше рассуждения и примеры, мы мо-
жем определить корректирующую способность линейного кода сле-
дующим образом.
Линейный двоичный (п, к)-код с минимальным расстоянием Хэм-
минга dmin > 2t + 1 может обнаружить dm\n — 1 ошибок и исправить
3
t ошибок.

2.4-2. Совершенные коды и граница Хэмминга
На рис. 2.5 изображен случай, когда все возможные принимаемые
векторы г принадлежат областям декодирования кодовых слов.
Коды, в которых непересекающиеся сферические области деко-
дирования охватывают все векторное пространство размерности п
называются совершенными или плотноупакованными.
При использовании совершенных кодов всегда возможна коррек-
ция ошибок (не обязательно правильная). Помимо кодов Хэмминга,
в настоящее время известно мало совершенных кодов.
Найдем соотношение между параметрами совершенных двоич-
ных (п, к)- кодов, способных исправлять t ошибок. Будем исходит из
того, что область декодирования совершенного (п,/г)-кода с d m j n =
2t+l образуют 2к непересекающихся сфер радиуса t в n-мерном век-
торном пространстве. Каждая сфера содержит все n-мерные векто-
ры, находящиеся на расстоянии I от соответствующего кодового сло-
ва, причем, 0 < I < t. Таким образом, каждой сфере принадлежит
ровно



п- мерных векторов.
Так как общий объем непересекающихся сфер не может превы-
шать объем n-мерного векторного пространства, для двоичных кодов
имеем
(2.26)
г=о ^ ' ^


?)• (2-27)
N
(=о '
3
Если код исправляет все ошибки кратности и < t, то области декодирования
представляют собой сферы радиуса t в n-мерном пространстве. - Прим. перев.
2.4- Свойства линейных блоковых кодов

Равенство имеет место только для совершенных двоичных кодов.
Выражение (2.27) называется границей Хэмминга. Граница Хэммин-
га является нижней оценкой необходимого числа проверочных сим-
волов двоичного кода длины п, способного исправлять t ошибок.
Из (2.27) следует, что рассмотренный нами (7,4)-код Хэмминга
является совершенным, так как

(2.28)
(=0

2.4-3. Вероятность ошибки декодирования
Исходя из предыдущих рассуждений, мы можем определить вероят-
ность необнаружимой ошибки. На самом деле, ошибка не обнаружи-
вается, если посланное кодовое слово в канале переходит в другое
кодовое слово. Из свойства замкнутого векторного пространства от-
носительно операции сложения кода С следует, что в этом случае
сама ошибка должна являться кодовым словом. Таким образом, ве-
роятность необнаружимой ошибки определяется суммой вероятно-
стей независимых событий е = v$, где V; 6 С и 1 < г < 2fc. Так как
мы рассматриваем ДСК без памяти с вероятностью ошибки Ре, ве-
роятность события, например, е = (0011010), где (0011010) - кодовое
слово из табл. 2.1, равна Р^(1 — Ре)4. Обозначим через А, число ко-
довых слов (п, &)-кода С веса г. Тогда вероятность необнаружимой
ошибки для кода С равна

Р — V4 APi(\ — P\n˜i (I 2Q^


Для (7,4)-кода Хэмминга значения Ai (распределения весов) можно
получить из таблицы 2.1. Имеем Ло = l,Ai = Ai = 0, A3 = А4 =
7, А5 = 0, А§ = 0, Ач = 1. Если вероятность одного двоичного симво-
ла Ре известна, то можно найти вероятность необнаружимой ошибки,
используя (2.29).
Не зная распределения весов, вероятность необнаружимой ошиб-
ки можно оценить сверху как
п

(2* - l)i^""°. (2.30)


Пример: Передача данных с использованием (7,4)-кода Хэмминга.
' 146 Глава 2. Линейные блоковые коды

Данные кодируются (7,4)-кодом Хэмминга и передаются по ка-
налу с АБГШ. Отношение сигнал/шум в канале равно 6 дБ, что
эквивалентно вероятности ошибки двоичного символа, равной 0,023.
Скорость передачи - 16 кбйт/сек. Если при декодировании обнару-
живается ошибка, то по сигналу переспроса производится повторная
передача кодового слова.

1. Какова вероятность, что кодовое слово будет приниматься без
ошибок?

2. Какова вероятность необнаружимой ошибки?

3. Определите среднюю «эффективную» скорость в битах (т.е
среднее число передаваемых информационных бит в секунду).

4. Сравните «эффективную» скорость с максимальной теорети-
чески достижимой.

Решение.
1. Кодовое слово будет передаваться без ошибок, если все 7 двоич-
ных символов будут переданы верно. Для ДСК без памяти с вероят-
ностью ошибки на символ Ре, вероятность безошибочной передачи
кодового слова равна
Рс = (1 - Ре)7. (2.31)
Для канала с АБГШ вероятность Ре определяется как функция от
SNR и равна




Подставляя Ре в (2.31), получаем

Рс = (1-0,023)7«0,85. . (2.33)

2. Вероятность необнаружимой ошибки получим из (2.29)

Р г = 7 0 , 0 2 3 3 0 , 9 7 7 4 + 7-0,023 4 -0,977 3 + 0,023 7 «7,9-10˜ 5 . (2.34)

Верхняя оценка Рг (2.30) дает для сравнения

(2к - l)P e d m i " w 15 • 0,023 3 « 18 • 10" 5 . (2.35)

3. Ввиду пренебрежимо малой вероятности необнаруженной ошибки,
будем считать, что в среднем 85% кодовых слов принимается верно
2.4- Свойства линейных блоковых кодов

без переспроса. Учитывая также, что доля информационных бит в
кодовом слове равна k/п получаем, что при скорости передачи Яь
эффективная скорость равна
к _• 4 • 0,85 • 16 кбит/сек _ _ ,. , .
!
Rb,eff = -PcRb « = « 7,77 кбит/сек. (2.36)
Замечание. Выбранное в примере SNR, равное 6 дВ, приводит к
недопустимо высокой вероятности ошибки на бит. Недопустимо
высокими являются также потери эффективной* скорости передачи.


4. Пропускная способность ДСК без памяти была рассмотрена в пер-
вой части этой книги. При вероятности ошибки двоичного символа
е, равной е = Ре, пропускная способность канала на один передава-
емый двоичный символ составляет

С д с к = 1 бит - Нь{е) = 0,842 бит. (2.37)

При заданной скорости 1& кбит/сек максимально достижимая эф-
фективная скорость передачи информации с пренебрежимо малой
вероятностью ошибки равна

Лтах < 13,4 кбит/сек, (2.38)

что почти в два раза превышает величину из (2.36).

В рассмотренном примере мы использовали зависимость вероят-
ности ошибочного бита от соотношения сигнал/шум (SNR) при пе-
редаче данных по каналу с АБГШ. Здесь мы сталкиваемся с «энер-
гетическим» аспектом цифровой передачи информации. Рассмотрим
этот аспект более подробно.
Будем исходить из постоянства некоторых параметров передачи.
Пусть этими параметрами являются эффективная скорость переда-
чи данных и средняя мощность передатчика. Пусть, далее, передача
информации осуществляется по каналу с аддитивным белым гаус-
совским шумом (АБГШ) и прием информации производится с при-
менением согласованных фильтров. В таком канале SNR оказыва-
ется пропорциональным длительности двоичного символа, поэтому,
при" постоянной мощности передатчика переход от четырех двоич-
ных символов (передача без кодирования) к семи символам ((7,4)-код
Хэмминга ) внутри фиксированного интервала времени эквивален-
тен уменьшению SNR в 7/4 раза, что равно, приблизительно, 2,4 дБ.
Глава 2. Линейные блоковые коды

И, наоборот, SNR на один двоичный символ при передаче без коди-
рования на 2,4 дБ выше, чем при использовании (7,4)-кода Хэмминга
и составляет, в нашем случае, 8,4 дБ. (Здесь мы даже не учитыва-
ем вероятность переспроса при передаче с кодированием). Согласно
(2.32), SNR, равному 8,4 дБ, соответствует вероятность ошибки на

<< Предыдущая

стр. 25
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>