Материал: 636_Nosov_V.I._Seti_radiodostupa_CH.1_
23 D(X) |
|
|
|
X6 + + X4 |
|
|
|
|
|
|
X3 + X2 + 1 |
|
|
|
|
|
P(X) |
||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
X6 + X5 + |
X3 |
|
|
|
X3 + X2 + 1 |
|
|
|
|
|
Q(X) |
||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X5 + X4 + X3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
X5 + X4 + |
|
|
X2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X3 + X2 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
X3 + X2 |
+ 1 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
R(X) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Рис. 4.9 Получение остатка от деления на порождающий полином |
||||||||||||||||||||
Z(X) |
|
|
|
X6 |
|
|
|
|
|
|
X3 + X2 + 1 |
|
|
|
|
|
|
P(X) |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
X6 + X5 + |
X3 |
|
|
|
X3 + X2 + 1 |
|
|
|
|
|
Q(X) + B(X) |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X5 + + X3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
X5 + X4 |
+ |
X2 |
|
|
|
|
|
|
X4 |
+ X3 + X2 |
|
|
|
|
|
|
X4 + X3 + |
|
X |
|
|
|
|
|
|
|
X2 |
+ X |
|
|
S(X) |
|
|
|
|
|
|||
Рис. 4.10 Получение синдрома ошибки
Таким образом, значение синдрома для рассматриваемого случая S = 110. Остальные значения синдрома, приведенные в таблице 4.4 б, вычисляются аналогично.
Теперь предположим, что на приемной стороне был получен блок
1101101, |
или Z(X ) X 6 |
X 5 X 3 X 2 |
1. Используя |
уравнение (4.19), |
||||||||||
получим значение синдрома рисунок 4.11. |
|
|
|
|
|
|
||||||||
Z(X) |
|
|
|
X6 |
+ X5 + |
X3 + X2 + 1 |
|
X3 + X2 + 1 |
|
|
|
P(X) |
||
|
|
|
|
|
|
|||||||||
|
|
|
|
|||||||||||
|
|
|
|
X6 |
+ X5 + |
X3 |
|
X3 + X2 + 1 |
|
|
B(X) |
|||
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X2 + 1 |
|
S(X) |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||||
Рис. 4. 11 Получение синдрома из Z(X)
Следовательно, значение синдрома S = 101. Используя данные таблицы
4.4 б, получим Е = 0001000. Тогда T 1101101 0001000 1100101. Поэтому,
согласно таблице 4.4 а, был передан блок данных 1100.
4.4 Код Голея
121
Код Голея - это двоичный линейный код (23, 12) с dmin = 7.
Одним из наиболее практичных блочных кодов является расширенный двоичный линейный код Голея (24, 12) с dmin=8 получается из кода Голея путем добавления ко всем кодовым комбинациям проверочного символа.
Таблица 4.4 Циклический код (7, 4) с коррекцией однобитовых ошибок
а) Таблица используемых кодовых слов |
||
Блок данных |
|
Кодовое слово |
0000 |
0000000 |
|
0001 |
0001101 |
|
0010 |
0010111 |
|
0011 |
0011010 |
|
0100 |
0100011 |
|
0101 |
0101110 |
|
0110 |
0110100 |
|
0111 |
0111001 |
|
1000 |
1000110 |
|
1001 |
1001011 |
|
1010 |
1010001 |
|
1011 |
1011100 |
|
1100 |
1100101 |
|
1101 |
1101000 |
|
1110 |
1110010 |
|
1111 |
1111111 |
|
б) Таблица синдромов, соответствующих однобитовым ошибкам |
||
Ошибочная комбинация |
|
Синдром |
0000001 |
|
001 |
0000010 |
|
010 |
0000100 |
|
100 |
0001000 |
|
101 |
0010000 |
|
111 |
0100000 |
|
011 |
1000000 |
|
110 |
Использование расширенного кода Голея (24, 12) дает скорость
кодирования R |
1 |
, реализовать которую проще (с точки зрения |
c |
2 |
|
|
|
использования двоичной логики), чем обычный код Голея (23, 12) со скоростью
кодирования Rc |
12 |
23 |
. Расширенный код Голея значительно мощнее |
|
|||
|
|
|
рассмотренного ранее кода Хэмминга. Цена, которую приходится платить за повышение эффективности кода, заключается в более сложном декодере и,
122
соответственно, более высокой скорости передачи и более широкой полосе, занимаемой сигналом. Для расширенного кода Голея dmin 8 , поэтому, исходя
из уравнения (3.16), можно сказать, что код гарантирует исправление всех трехбитовых ошибок.
Линейный код Голея (23, 12) можно генерировать посредством порождающего полинома
P(X ) X11 X 9 X 7 X 6 X 5 X 1.
4.5 Коды БЧХ
Коды Боуза-Чоудхури-Хоквенгема (Bose-Chadhuri-Hocquenghem — ВСН, БЧХ) являются результатом обобщения кодов Хэмминга, которое позволяет исправлять множественные ошибки. Они составляют мощный класс циклических кодов, который обеспечивает достаточную свободу выбора длины блока, степени кодирования, размеров алфавита и возможностей коррекции ошибок.. Коды БЧХ очень важны, поскольку при блоках, длина которых равна порядка несколько сотен бит, коды БЧХ превосходят своими качествами все другие блочные коды с той же длиной блока и степенью кодирования. В наиболее часто применяемых кодах БЧХ используется двоичный алфавит и блок кодового слова
Длина блока |
n = 2m -1 |
|
Количество контрольных битов |
n – k |
mt |
Минимальное расстояние |
dmin |
2t +1 |
С помощью такого кода можно исправить все слова, содержащие t (или менее) ошибок. Порождающий многочлен кода БЧХ можно создать в
соответствии с (3.24) и (3.25) из множителей полинома (X 2m 1 1) . |
|
||
В таблице 4.5 приведены параметры кодов БЧХ (n, k, t) для 7 n |
255. |
||
В таблице 4.6 приводятся наиболее часто употребляемые при создании |
|||
кодов БЧХ генераторные (производящие) полиномы P( X ) с разными |
|||
значениями n,k и t |
для блоков длиной до 255. |
Коэффициенты полиномов |
|
P( X ) представлены |
многочленом, двоичными и |
восьмеричными |
числами. |
Восьмеричные числа оформленными так, что при преобразовании их в двоичные символы крайние правые разряды отвечают коэффициенту нулевой степени в P( X ) . С помощью таблицы 4.5 можно легко проверить свойство
циклического кода – генераторный полином имеет порядок (п – k)
123
Так, коэффициентами порождающего полинома для кода (15, 5, 3) в восьмеричной форме является число 2467, что соответствует двоичной форме 10 100 110 111. В результате перехода от записи двоичной формы
представления порождающего полинома к записи многочлена получим
|
|
|
|
|
X (P) X10 |
X 8 |
X 5 |
X 4 |
X 2 |
X 1. |
|
|
|
||
|
Таблица 4.5 Параметры кодов БЧХ |
|
|
|
|
|
|
|
|||||||
n |
k |
t |
|
n |
k |
t |
n |
k |
t |
n |
k |
t |
n |
k |
t |
7 |
4 |
1 |
63 |
30 |
6 |
127 |
64 |
10 |
255 |
207 |
6 |
255 |
99 |
23 |
|
15 |
11 |
1 |
|
|
24 |
7 |
|
57 |
11 |
|
199 |
7 |
|
91 |
25 |
|
7 |
2 |
|
|
18 |
10 |
|
50 |
13 |
|
191 |
8 |
|
87 |
26 |
|
5 |
3 |
|
|
16 |
11 |
|
43 |
14 |
|
187 |
9 |
|
79 |
27 |
31 |
26 |
1 |
|
|
10 |
13 |
|
36 |
15 |
|
179 |
10 |
|
71 |
29 |
|
21 |
2 |
|
|
7 |
15 |
|
29 |
21 |
|
171 |
11 |
|
63 |
30 |
|
16 |
3 |
127 |
120 |
1 |
|
22 |
23 |
|
163 |
12 |
|
55 |
31 |
|
|
11 |
5 |
|
|
113 |
2 |
|
15 |
27 |
|
155 |
13 |
|
47 |
42 |
|
6 |
7 |
|
|
106 |
3 |
|
8 |
31 |
|
147 |
14 |
|
45 |
43 |
63 |
57 |
1 |
|
|
99 |
4 |
255 |
247 |
1 |
|
139 |
15 |
|
37 |
45 |
|
51 |
2 |
|
|
92 |
5 |
|
239 |
2 |
|
131 |
18 |
|
29 |
47 |
|
45 |
3 |
|
|
85 |
6 |
|
231 |
3 |
|
123 |
19 |
|
21 |
55 |
|
39 |
4 |
|
|
78 |
7 |
|
223 |
4 |
|
115 |
21 |
|
13 |
59 |
|
36 |
5 |
|
|
71 |
9 |
|
215 |
5 |
|
107 |
22 |
|
9 |
63 |
Таблица 4.6 Порождающие многочлены кодов БЧХ
|
|
|
|
|
|
|
Порождающий полином |
|
|||
n |
k |
t |
|
|
многочлен |
|
|
Двоичный код |
Восьмеричный |
||
|
|
|
|
|
|
|
|
|
|
|
код |
7 |
4 |
1 |
X 3 |
X |
1 |
|
|
|
|
1011 |
13 |
15 |
11 |
1 |
X 4 |
X |
1 |
|
|
|
|
10011 |
23 |
15 |
7 |
2 |
X 8 |
X 7 |
X 6 |
X 4 |
1 |
|
|
111010001 |
721 |
15 |
5 |
3 |
X 10 |
X 8 |
X 5 |
X 4 |
X 2 |
X |
1 |
10100110111 |
2467 |
31 |
26 |
1 |
X 5 |
X 2 |
1 |
|
|
|
|
100101 |
45 |
31 |
21 |
2 |
X 10 |
X 9 |
X 8 |
X 6 |
X 5 |
X 3 |
1 |
11101101001 |
3551 |
31 |
16 |
3 |
|
|
|
|
|
|
|
|
107657 |
31 |
11 |
5 |
|
|
|
|
|
|
|
|
5423325 |
31 |
6 |
7 |
|
|
|
|
|
|
|
|
313365047 |
63 |
57 |
1 |
X 6 |
X |
1 |
|
|
|
|
1000011 |
103 |
63 |
51 |
1 |
|
|
|
|
|
|
|
|
12471 |
Более полный список порождающих полиномов для кодов БЧХ можно найти в [20].
124
Для декодирования сигналов кода БЧХ можно использовать поиск в таблицах разрешенных кодовых слов и синдромов ошибок (подобных таблице 4.4 для циклического кода (7, 4)). На настоящее время разработано достаточно большое количество алгоритмов, требующих меньше памяти, чем прямой поиск в таблице. Однако сложность этих алгоритмов увеличивается как квадрат количества ошибок, которые нужно исправить.
4.6 Коды Рида-Соломона
Коды Рида-Соломона (Reed-Solomon codes – RS codes) – это широко используемый подкласс недвоичных кодов БЧХ.
Длина символа |
m бит |
Длина блока |
n = (2m -1) символов = m(2m -1) бит |
Длина блока данных |
k символов |
Размер контрольного кода |
n – k = 2t символов = m(2t) бит |
Минимальное расстояние |
dmin = (2t + 1) символов |
При использовании кодов Рида-Соломона данные обрабатываются порциями по m бит, именуемыми символами. Код (n, k) характеризуется следующими параметрами
Таким образом, алгоритм кодирования расширяет блок k символов до размера n , добавляя (n – k) избыточных контрольных символов. Как правило, m > 1 является степенью 2, широко используется значение m = 8.
Коды Рида-Соломона удобны для исправления пакетов ошибок. Данный тип кодов характеризуется высокоэффективным использованием избыточности, длина блоков и размеры символов могут легко приспосабливаться под сообщения разных размеров. Кроме того, для таких кодов существуют эффективные методы кодирования.
Коды Рида-Соломона (n, k) определены на m-битовых символах при всех n и k , для которых
0 k n 2m 2, |
(4.22) |
Где k число информационных бито, подлежащих кодированию, а n – число бит в закодированном блоке. Для большинства кодов Рида-Соломона (n, k)
(n,k) (2m 1,2m 1 2t), |
(4.23) |
125