Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
4.ОБЩИЕ ПРИНЦИПЫ ПРОСТЫХ ПРЕОБРАЗОВАНИЙ ГРУППОВЫХ
ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
4.1. Классификация и краткая характеристика простых преобразований
групповых линейных блоковых кодов
В теории кодирования, а также в реальных системах связи, используется
достаточно большое количество простых преобразований групповых линейных
блоковых кодов (ГЛБК), которые незначительно изменяют исходный линейный
код, но образуют новый код. Если новый код также является линейным, то эти
преобразования соответствуют небольшим изменениям порождающей матрицы
G
k,n
(х). Например, можно добавить в эту матрицу либо столбец, либо строку,
или наоборот удалить либо столбец, либо строку, или одновременно выбросить
и столбец и строку. Все эти изменения кода легко описать, хотя может оказать-
ся, что данные преобразования непросто найти для конкретного применения
кода.
Длину кодовой последовательности “n” можно увеличивать как за счет
увеличения количества информационных символов, т.е. “k”, так и за счет уве-
личения количества проверочных символов, т.е. “l”. В первом случае – преоб-
разование кода называется удлинением, во втором случае – расширением кода.
Оба эти термина объединяются в один – увеличение кода.
Различают шесть основных преобразований кода, а именно [3,4]:
Сущность данных простых преобразований групповых линейных блоко-
вых кодов (ГЛБК) состоит в следующем:
Преобразование кода
Расширение
Удлинение
Выкалывание кодо-
вых координат
Укорочение
Пополнение
Код с
выбрасыванием
1) расширение кода – это увеличение длины кодовой последовательности за
счет добавления (увеличения) новых проверочных символов, что приводит к
увеличению ранга порождающей матрицы G
k,n
(х); ранг (размер) матрицы
G
k,n
(х)увеличивается за счет увеличения количества столбцов G
k,n
(х)→
→G
k,n+1
(х);
2) удлинение кода – это увеличение длины кодовой последовательности за
счет добавления новых информационных символов, что приводит к увели-
чению обоих размеров порождающей матрицы G
k,n
(х), т.е. количество
строк и столбцов G
k,n
(х) на одно и тоже число, т.е. G
k,n
(х) → G
k+i,n+i
(х),
где i = 1,2 …;
3) выкалывание кодовых координат – это уменьшение длины кода, т.е. “n”
за счет удаления (уменьшения) количества проверочных символов, что при-
водит к уменьшению большего размера порождающей матрицы G
k,n
(х), т.е. к
уменьшению количества столбцов G
k,n
(х) → G
k,n-1
(х), где i + 1, 2 … ;
4) укорочение кода – это уменьшение длины кода, т.е. “n” за счет удаления
(уменьшения) количества информационных символов, что приводит к
уменьшению обоих размеров порождающей матрицы G
k,n
(х), т.е. строк и
столбцов G
k,n
(х)на одно и тоже число;
5) пополнению кода – это увеличение числа информационных символов кода
без увеличения длины кода, что приводит к увеличению меньшего разряда
порождающей матрицы G
k,n
(х), т.е. увеличивается количество строк поро-
ждающей матрицы G
k,n
(х) → G
k+i,n
(х): количество столбцов, т.е. “n” оста-
ется без изменения;
6) код с выбрасыванием – это процесс преобразования, предусматривающий
уменьшение числа информационных символов без изменения длины кода,
т.е. n =const, что приводит к уменьшению меньшего размера порождающей
матрицы G
k,n
(х), т.е. к уменьшению количества строк G
k,n
(х), а количест-
во столбцов G
k-1,n
(х) остается без изменения.
Эти шесть линейных преобразований кодов можно проиллюстрировать
на примере (n, k, d
0
) = (7,4,3) – кода Хэмминга с образующим полиномом Р (х)=
х
3
+ х + 1 (рис. 4.1)
Рис.4.1. Схема возможных преобразований ГЛБК
Для данного типа помехоустойчивого кода сущность шести линейных пре-
образований кода состоит в следующем [3,4].
Процедура расширения кода реализуется путем добавления проверочных
символов. Дополнительные проверочные символы следует выбирать так, чтобы
они улучшали весовую структуру кода. Обычным случаем такой модификации
кода является введение общей проверки на четность: значение соответствую-
щего проверочного символа равно остатку от деления первоначального кодово-
го слова на полином P(x)=(x-1). При добавлении общей проверки на четность
вес (w
k,n
) каждой кодовой последовательности становится четным и d
0
увели-
чивается на единицу, т.е., например, d
0
=3 становится равным d
0
=d
0
+1=3+1=4.
Процедура выкалывания кода реализуется путем удаления некоторых
проверочных символов, т.е. уменьшением количества проверочных символов.
Нециклический код (8,4,4)
=
11101000
01110100
11010010
11111111
Н(х)
(n,k,d
0
) = (7,4,3) –
циклический
код, Р (х)= х
3
+ х + 1
=
1111100
0111010
1101001
Н(х)
Циклический код (7,4,3)
Р (х)= (х + 1) (х
3
+ х + 1)
=
1011000
1110100
1100010
0110001
Н(х)
Расшир
е
ние
Пополн
е
ние
Выкалыв
а
ние
Укороч
е-
Удлин
е-
Выбрасыв
а
ние
Эта процедура обратна процедуре расширения кода. Так, выкалывание расши-
ренного кода (8,4,4) приводит к (n,k,d
0
) = (7,4,3) - коду Хэмминга. Если не по-
заботится об аккуратном выборе удаляемого проверочного символа, то в ре-
зультате операции выкалывания d
0
уменьшается на единицу.
Процедура выбрасывания кода реализуется путем удаления некоторых
кодовых символов. Для ЦК эта процедура проводится путем умножения P(x) на
дополнительный сомножитель (x
n
-1). Наиболее часто встречается код с выбра-
сыванием, порождённый полином P(x)=P(x)(x-1); кодовыми словами (последо-
вательностями) этого кода являются все последовательности чётного веса из
первоначального кода. Так, например, в результате выбрасывания из (n,k,d
0
) =
(7,4,3) - кода Хэмминга, получаем (n',k',d
0
' ) = (7,4,3) - код порождённый мно-
гочленом P(x)=(x+1)(x
3
+x+1).
Процедура пополнения кода реализуется путем добавления новых кодо-
вых слов (последовательностей). ЦК, порождённый полином P(x), может быть
пополнен до кода той же длины, образующий полином которого является неко-
торым множителем P(x). Если, например, P(x) содержит сомножитель (x-1), то
пополненный код будет порождаться полиномом P(x)/(x-1).
Процедура удлинения кода реализуется путем добавления дополнитель-
ных информационных символов. Если начать с ЦК, для которого P(x) делится
на (x-1), то удлинение этого кода проводится в два этапа:
– сначала код надо дополнить (пополнить) до кода порожденного полиномом
ρ(x)/(x-1); это соответствует добавлению к коду слова (последовательности) со-
стоящего целиком из единиц;
– далее полученный код нужно расширить, добавив общую проверку на чет-
ность.(В большинстве случаев такая процедура может быть проведена без
уменьшения d
0
).
Процедура укорочения кода реализуется путем удаления (уменьшения)
информационных символов. В ЦК такую процедуру обычно проводят, пологая
начальные информационные символы каждого кодового слова (последователь-
ности) равными “0”; d
0
=const.
4.2. Общие принципы простых преобразований групповых линейных
блоковых кодов
4.2.1. Общие принципы построения укороченных циклических кодов и
их свойства
Любой систематический ЦК с параметрами (n,k,d
0
) можно укоротить, а
именно перейти от кода (n,k,d
0
) к коду с параметрами(n-L,k-L,d
0
), с выбрасы-
ванием “L” информационных символов (позиций) в каждой кодовой последова-
тельности. Как правило L<k и выбрасывается, т.е. не передаются в канал связи
L старших разрядов (символов) кодовой последовательности F(x), которые при
укорочении кода полагаются равными “0” и поэтому в канал связи не переда-
ются. Параметр L носит название шага укорочения. При декодировании деко-
дер должен восстановить непередаваемые нулевые символы, так как декодиро-
вание осуществляется на полной длине “n” кода.
Если минимальное кодовое расстояние исходного кода равно d
0
, то и у
укороченного кода оно будет не меньше d
0
. Аналогично, если исходный код
позволяет исправлять пакеты ошибок длинны “t
n
” двоичных символов, то уко-
роченный код также позволяет исправлять пакеты ошибок длинны “t
n
” (или
более).
С помощью укорочения и перемежения можно построить большой набор
хороших кодов, исправляющих пакеты ошибок. Укороченный ЦК уже не явля-
ется ЦК, а относится к псевдоциклическому коду. Однако, укороченный ЦК
все-таки обладает алгебраической структурой подмножества соответствующего
кольца. В то время как ЦК является идеалом кольца многочленов (полиномов)
по модулю x
n-1
, то укороченный ЦК является идеалом кольца полиномов по
модулю некоторого полинома f(x) степени n'=n-L.
Рассмотрим пример на построение укороченного ЦК. Построение укоро-
ченного ЦК можно выполнить с использованием как порождающей матрицы
G
k,n
(х), так и проверочной матрицы H
l,n
(х).
Пример 4.1. По заданной порождающей матрице ЦК с параметрами (n, k,
d
0
) = (8,4,4) построить укороченный на L=2 двоичных символа код с парамет-
рами (n'=6, k'=2, d
0
'). Определить d
0
'.
Решение:
а) пусть задана порождающая матрица вида
; (4.1)
б) для построения порождающей матрицы укороченного кода G
k-L,n-L
(х)=
=G
2,6
(х) необходимо исключить из матрицы G
4,8
(х) две строки которые
должны начинаться с ненулевых символов и на старших позициях этих
строк должно быть L-2 (допускается L-1)ненулевых двоичных символов, а
затем исключить L=2 левых столбцов
В результате получаем следующую порождающую матрицу укороченного
кода:
; (4.2)
в) определяем d
0
' укороченного кода. Так как вес каждой строки равен w
стр
=3,
а вес проверочной части строки w
пр,стр
=2, то следовательно, укороченный
код имеет следующие параметры: (n', k', d
0
')=(6,2,3).
Пример 4.2. Построить укороченный ЦК с использованием проверочной
матрицы следующего вида:
=
01100001
01110010
01010100
00111000
)(
8,4
xG
=⇒
=
010101
001110
)(
6,2
01100001
01110010
01010100
00111000
)(
8,4
xGxG
. (4.3)
Решение:
а) принимаем шаг укорачивания кода L=2 двоичного символа;
б) при построении укороченного кода с использованием проверочной матрицы
H
l,n
(x) необходимо исключить из проверочной матрицы L правых столб-
цов, т.е. в данном примере L=2 столбца;
в) следовательно, исключая из проверочной матрицы (4.3) два правых столбца
получаем следующую проверочную матрицу укороченного кода:
. (4.4)
4.2.2. Общие принципы построения кодов с использованием процедуры
“расширения кода” и их основные свойства
Как уже отмечалось выше, линейные преобразования можно использовать
для модификации известных кодов, чтобы сделать их приемлемыми (подходя-
щими) для каких-либо конкретных приложений, а также получения “новых”
классов (подклассов) “хороших” кодов.
Любой (n, k, d
0
) – код с нечетным минимальным кодовым расстоянием
можно расширить до (n+1, k, d
0
*
+1) – кода путем добавления к каждому ко-
довому слову (кодовой последовательности) суммы всех его двоичных симво-
лов в качестве проверки на четность. Это возможно потому, что в случае, когда
исходная кодовая последовательность имеет нечетный вес, то к ней будет до-
=
10000000
11001110
00101101
00010111
)(
8,4
xH
=⇒
=
001110
101101
010111
)(
6,4
10000000
11001110
00101101
00010111
)(
8,4
xHxH
бавляться единичный символ, т.е. логическая единица. Следовательно, все ко-
довые последовательности веса d
0
становятся кодовыми последовательностями
веса d
0
*
+1. В этом случае, если H(x) – проверочная матрица исходного кода,
то расширенный код будет иметь проверочную матрицу вида [3,4]:
, (4.5)
где 11…1 – строка, состоящая из одних логических единиц,
– столбец, состоящий из одних логических нулей.
В частности, каждый(2
l
-1,2
l
-1-l) – код Хэмминга может быть расширен
до (2
l
,2
l
-l) – кода исправляющего одну ошибку (t
исп
=1
двоичный символ) и
обнаруживающего двукратную ошибку (t
обн
=2 двоичных символа). Этот код
также называется кодом Хэмминга.
Пример 4.3. Построить расширенный код Хэмминга с параметрами (2
l
,2
l
-
l)=(2
4
,2
4
-4)=(16,11,4), если исходный код Хэмминга имеет параметры (2
l
-1,2
l
-1-
l)=(2
4
-1,2
4
-1-4)=(15,11,3), и проверочная матрица имеет следующее построение:
.
=
0
)(
0
111
)('
.
.
.
xH
xH
...
0
0
0
.
.
.
=
101010101010101
110011001100110
111100001111000
111111110000000
)(
15.4
xH
0
n
α
2
α
1
α
0
α =⊕⊕⊕⊕ K
0
n
α
2
α
1
α
0
α =⊕⊕⊕⊕ K
Решение:
а) в каждую кодовую последовательность должен быть введен дополнитель-
ный проверочный символ, обозначим его через α
0
, осуществляющий общую
проверку на четность, т.е.
б) введение этого дополнительного проверочного символа необходимо учесть
в проверочной матрице исходного кода путем приписания слева логическо-
го нуля к каждой строке исходной матрицы, т.е. впереди каждой строки
приписать нулевой символ;
в) к получившимся строкам матрицы сверху приписывается строка, состоящая
из одних логических единиц. Следовательно, проверочная матрица будет
иметь следующее построение:
.
При использовании стандартного алгоритма декодирования и при наличии
ошибок возможны две основные ситуации:
первая – синдром совпадает с одним из столбцов матрицы H
5,16
(x) и тогда
ошибка исправляется. В случае одиночно
й ошибки добавленное равенство
нарушается, а остальные синдромные символы
S
1
,S
2
,S
3
,S
4
– образуют номер позиции столбца проверочной матрицы H
5,16
(x) и,
следовательно, номер ошибочного информационного символа;
вторая – синдром не совпадает ни с одним из столбцов матрицы H
5,16
(x) и
синдром не равен нулю. Это означает, что в кодовой последовательности име-
ется две ошибки. Если произойдет две или более ошибок, то равенство
не нарушается, а структура синдрома S
1
…S
4
не
совпадет ни с одним из столбцов матрицы H
5,16
(x) и не будет неравной нулю.
Полученный(n, k, d
0
)=(16,11,4) – код Хэмминга уже является нециклическим
;0
n
α
2
α
1
α
0
α =⊕⊕⊕⊕ K
=
1010101010101010
1100110011001100
1111000011110000
1111111100000000
1111111111111111
)(
16.5
xH
кодом. По аналогичному принципу построен нециклический (n, k, d
0
)=(8,4,4) –
код в схеме рис.4.1.
4.2.3. Общий принцип построения кодов с использованием процедуры
“выкалывания кодовых координат”
По своей сущности эта процедура обратна процедуре расширения кодов,
т.е. новый код может быть получен из исходного кода путем удаления некото-
рых проверочных символов. Так, например, из проверочной матрицы (4.3)
(8,4,4) – кода, удалив первый справа столбец и первую строку, получим прове-
рочную матрицу циклического (n,k,d
0
) = (7,4,3) – кода Хэмминга; если не поза-
ботиться об аккуратности выбора удаляемого проверочного символа, то в ре-
зультате операции “выкалывания” кодовое расстояние уменьшится на единицу,
что и видим на схеме рис.4.1.
4.2.4. Общий принцип построения кодов с использованием процедуры
“выбрасывания кодовых последовательностей”
Процедура выбрасывания кодовых последовательностей осуществляется
путем удаления некоторых последовательностей. Для ЦК эта процедура легко
проводится путем умножения образующего полинома P(x) на дополнительный
сомножитель (x
n
-1). Наиболее часто встречается помехоустойчивый код с вы-
брасыванием, образованный полиномом P(x)(x
l
-1), кодовыми последовательно-
стями которого являются все последовательности четного веса из исходного
кода. Так, в результате выбрасывания из (7,4,3) – кода Хэмминга получается
(7,3,4) – код, образованный полиномом P(x)=(1+x)(1+x+x
3
).
Таким образом, чтобы построить новый код путем использования проце-
дуры “выбрасывания”, в проверочную матрицу исходного кода (например
(7,4,3) – кода, приведенного на схеме рис.4.1) ввести новый (дополнительный
или дополнительные столбцы проверочной части матрицы и соответственно