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

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

ОГЛАВЛЕНИЕ

Следующая >>

бит, равная Рь = 0,0043. Отсюда, вероятность безошибочной переда-
чи блока, содержащего 4 информационных символа, составляет

Рс = (1 - 0,0043)4 = 0,98. (2.39)

Отметим, что при постоянной мощности передатчика, применяя
кодирование, мы увеличиваем вероятность ошибки двоичного сим-
вола (в нашем случае от 0,0043 до 0,023). Однако, корректирующая
способность кода позволяет снизить результирующую вероятность
необнаружимой ошибки (в нашем случае с 1 —0,98 = 0,02 до 7,9-10˜5
на блок из четырех символов).
В настоящее время существует несколько критериев для оценки
эффективности кодирования. В спутниковой связи, например, чаще
всего пользуются энергетическим критерием. Сущность его в следу-
ющем: так как спутниковые линии связи близки к каналам с АБГШ,
вначале находится SNR на бит передаваемой информации, обеспечи-
вающее заданную вероятность битовой ошибки Рь при передаче без
кодирования.
Аналогичное SNR на кодовый символ подсчитываете для пере-
дачи с кодированием при условии BER = Рь, где Рь задано. После
этого, находится SNR на бит полезной информации с учетом скоро-
сти кода. Разность энергетических затрат на бит передаваемой ин-
формации при передаче без кодирования и с кодированием называ-
ется энергетическим выигрышем кода (ЭВК).
Замечание. Использование кодов большой длины с довольно слож-
ной алгебраической структурой в современных спутниковых линиях
связи позволяет достичь ЭВК — 6 - 8 дБ при Рь = 10˜5. Заметим,
что при снижении Рь ЭВК возрастает.

2.4-4- Коды Хэмминга
Коды Хэмминга образуют важное семейство простейших линейных
блоковых кодов. Для каждого натурального т > 3 существует дво-
ичный код Хэмминга со следующими параметрами:
Коды Хэмминга.
• длина кодовых слов п = 2т — 1
2-4- Свойства линейных блоковых кодов I49J

т
• число информационных разрядов к = 1 — 1 - т


• число проверочных разрядов т = п — к


• корректирующая способность t = l,d m j n = 3


• совершенные коды у/


Конструкция кодов Хэмминга определяется следующими свойства-
ми проверочной матрицы вида (2.15).



Так как минимальное расстояние кода Хэмминга d m i n = 3, все
столбцы проверочной матрицы должны быть попарно различ-
ными (проверочная матрица не должна содержать одинаковых
столбцов).


• Из d m i n = 3 следует также, что каждая строка порождающей
матрицы должна содержать как минимум три единицы, так
как строки порождающей матрицы в свою очередь являются
кодовыми словами. Если порождающая матрица представлена
в виде (2.14), то это значит, что строки матрицы Р должны
содержать как минимум две единицы. (Следовательно, это от-
Т
носится и к столбцам транспонированной матрицы Р )-


• Рассмотрим проверочную матрицу. Согласно (2.8), она имеет
вид H ( n _ f c ) x n = (In-fcPL(n-fc))- Матрица Р т содержит А столб-
;
цов и т = п — к строк. Используя двоичные символы «О» и «1»,
можно образовать 2т различных столбцов. Но, так как ранее
было сказано, что каждый столбец должен содержать как ми-
нимум две единицы, то следует отбросить один нулевой столбец
и т столбцов, содержащих по одной единице. Таким образом,
остается 2 т — т — 1 возможностей. Так как 2т — тп — 1 = кч мат-
рица Р т содержит ровно к столбцов, то все эти возможности
использованы. Отсюда следует, что столбцы транспонирован-
ной матрицы Р т представляют собой все возможные двоичные
Глава 2. Линейные блоковые коды

4
слова длины тп = п — к, содержащие не менее двух единиц.

Пример: (15,11)-код Хэмминга.
На примере (15,11)-кода Хэминга можно наглядно пояснить все
перечисленные выше особенности конструкции:

\
1000 1 0 0 1 01 1 0 1 1 1
0100 1 1 10 1 1 1 1
0 0 0
. (2.40)
Н 4x15
00
0010 1 1 1 1 1 1 1
0
0
1001 1 11 1 1 1 1
0 0 0
0
—у

14 Вес Хэмминга u« =2 шк=3 шд=4

По проверочной матрице с помощью (2.15) и (2.14) строится порож-
дающая матрица

/1100 10000000000\
011001000000000
0011 00100000000
1 0 1 1 0 0 0 10 0 0 0 0 0 0
0101 00001000000
100100000100000 . (2.41)
111000000010000
-0 111О0000001000
1011 00000000100
1101 00000000010
1111 0000 0000001
Pll


Пример: Передача данных с использованием (15,11)-кода Хэм-
минга.
4
Отметим, что п столбцов матрицы H m X n = ( I n - k P ^ X ( n _ t ) ) содержат все воз-
можные двоичные слова длины га, за исключением нулевого, т.е. п = 2 т — 1 и
все столбцы различны. Такое представление позволяет сразу же раскрыть метод
коррекции одиночных ошибок. В самом деле, уравнение синдромного декодиро-
вания (2.19) имеет вид s = е 0 Н т . Если е - вектор одиночной ошибки, то он
содержит только одну единицу в г-ом ошибочном разряде кодового слова. В этом
случае синдром (вектор s) представляет собой г-ый столбец матрицы Н. Так как
все столбцы матрицы Н различны, то п возможным позициям одиночной ошиб-
ки в кодовом слове соответствуют в точности п различных синдромов, поэтому,
по значению синдрома s можно однозначно определить номер разряда кодового
слова, в котором произошла одиночная ошибка, т.е. ее исправить. - Прим. перев.
2.4- Свойства линейных блоковых кодов 151

В данном примере мы сравниваем результаты использования для
передачи данных (15,П)-кода Хэмминга с ранее полученными ре-
зультатами для (7,4)-кода Хэмминга. Скорость (15,11)-кода суще-
ственно выше (7,4)-кода, так как Д(15,ц) = 15/11 « 0,73, а Д(7,4) =
4/7 « 0,57. Посмотрим, как изменятся другие параметры кодирова-
ния. Для этого выполним задания Д. 2. 3. из предыдущего примера.

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

Рс = (1 - Р е ) 1 5 - (2.42)

Для вероятности ошибки на двоичный символ Ре = 0,023, взятой из
предыдущего примера (2.32), имеем

Рс = (1 - 0,023) 15 « 0,705. (2.43)

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

(2* - l)/^ m i ° ж 2047 • 0,0233 « 0,025. (2.44)

3. При скорости передачи двоичных символов 16 кбит/сек, эффек-
тивная скорость передачи данных составляет

itnn 11 -0,705 -16 кбит/сек ^ . ,nlp,
Rb,ef/ = -PcRb ˜ « 8,27 кбит/сек. (2.45)
7Z

В приведенных расчетах мы исходили из одной и той же вероятности
ошибки двоичного символа Ре = 0,023 для (15,11)- и (7,4)-кодов.

Проведем аналогичные расчеты при одинаковой мощности пере-
датчика. В этом случае, потери энергетики на один символ по сравне-
нию с передачей без кодирования составляют для (15,11)-кода только
15
101og2 —- ˜ 1,4 д Б (для (7,4)-кода эта величина составляет 2,4 д Б
- см. предыдущий пример). Таким образом, отношению сигнал/шум
равному 7 д Б соответствует вероятность ошибки двоичного символа,
равная 0,013, поэтому

Рс = (1-0,013)15!«0,82, (2.46)

и вероятность необнаружения ошибки оценивается сверху как

(2* - 1)Р*""" « 2047 • 0,013 3 и 0,0045. (2.47)
152 Глава 2. Линейные блоковые коды

Эффективная скорость передачи также возрастает

11 0,82 • 16 кбит/сек
к
Rb,e./f = -РсЯъ « jg « 9,62кбит/сек. (2.48)


Условие неизменной мощности передатчика более близко к практике,
чем условие равенства вероятностей ошибки двоичных символов. По
сравнению с (7,4)-кодом, для (15,11)-кода мы получаем некоторый
выигрыш по эффективной скорости Rb,eff = 9,62 кбит/сек за счет
возрастания вероятности необнаружимой ошибки.
Рассмотренные примеры показывают, что выбор кода для каж-
дой конкретной системы должен осуществляться с особой тщатель-
ностью.

2.4-5. Расширенные коды Хэмминга
В этом разделе мы рассмотрим весьма полезное расширение кодов
Хэмминга. Оно заключается в дополнении кодовых векторов допол-
нительным двоичным разрядом таким образом, чтобы число единиц,
содержащихся в каждом кодовом слове, было четно. Коды Хэмминга
с проверкой на четность обладают следующими двумя преимуществами.

П
• Длины кодов увеличиваются с 2" — 1 до 2 , что удобно с точки
зрения хранения и передачи информации.

• Минимальное расстояние d m i n расширенных кодов Хэммин-
га равно 4 вместо 3, что дает возможность обнаруживать 3-
кратные ошибки.

Дополнительный разряд проверки на четность позволяет исполь-
зовать декодер в новом режиме - гибридном режиме обнаружения и
коррекции ошибок.
В качестве примера, рассмотрим расширение (15,11)-кода Хэм-
минга. Каждый кодовый вектор v = (щ,Ъ\,...,йщ) расширенного
(16,11)-кода Хэмминга получается из кодового вектора v = (г?о, V\,V2,
• • • > v\i) (15,11)-кода путем добавления дополнительного разряда про-
верки на четность, т.е.

v = («о, vi, ...,щь) (2.49)
= (v0,v0,vi,...,vu),

где
14
(2.50)
vo = Y,Vi-
i=0
2-4' Свойства линейных блоковых кодов

Проверочная матрица (16,11)-кода получается из проверочной мат-
рицы (15,11)-кода Хэмминга в два приема:
-допишем к матрице (15,11)-кода Хэмминга слева нулевой стол-
бец;
-дополним получившуюся матрицу строчкой, полностью состоя-
щей из одних единиц.
В результате получим

/1 1 1 1 1 1 11 1 1 1 1 1 1 1 1\
-
0100010010110111
0010011001011011 (2.51)
0001001110011101
V 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1/

При синдромном декодировании

I = v 0 Нт, (2.52)

причем, правая компонента равна
15
(2.53)
«О =
i=0
С учетом (2.49) и (2.50), получаем
15
(2.54)
г=0

Из (2.49) и (2.51) следует, что и другие компоненты синдрома s также

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

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

ОГЛАВЛЕНИЕ

Следующая >>