|
|
Т А Б Л И Ц А |
G.8 |
|
|
|
|
|
|
|
|
а) |
|
б) |
|
|
|
1 |
в) |
|
|
Передано |
1 0 1 0 0 1 0 1 0 0' 1 0 |
1 |
1 0 |
0 |
1 0 |
0 1 |
0 1 0 0 0 |
1 0 |
1 1 1 |
|
Принято |
1 П Т l o o i o i o o 1 0 1 | 0 0 0 1 0 0 1 о 1 о о о l j T j l l l |
|
|
|
Зарегистрирова |
1 j T j 1 о о о 1 о 1 1 1 0 |
1 j T j o |
0 |
1 0 |
0 1 |
o i o o o |
ofo] |
ООО |
|
но |
|
|
|
|
|
|
|
|
|
|
Анализ принятой |
1 Щ 1 |
о о |
1 о |
|
i [ F o |
комбинации |
+ |
|
|
+ |
|
|
|
|
|
0 |
1 0 |
11 |
0 |
1 |
0 |
0 |
1 |
|
1|0] 1 |
1 1 |
l |
l |
|
l j T j i |
информационного элемента (столбцы а я б). Если иска женный элемент расположен во второй половине кодовой комбинации, то при сложении по модулю два (столбец в) только одна пара элементов не совпадает, что указы вает на искажение проверочного элемента.
Основным недостатком инверсных кодов является их высокая избыточность.
§ 6 . 4 . СИСТЕМАТИЧЕСКИЕ (ГРУППОВЫЕ) КОДЫ
Систематическими (или линейными) называются та кие блочные разделимые (п, 1г)-коды, в которых k разря дов (обычно первые) представляют собой комбинации
простого кода, а последующие (п—k) |
разрядов являют |
ся проверочными (корректирующими) и образуются с |
помощью линейных операций над |
информационными |
[66]. Основным свойством двоичных систематических ко
|
|
|
|
|
|
|
|
|
дов, определяющим |
принцип |
их построения, |
является |
то, |
что |
двух или |
нескольких |
'разрешенных кодовых |
комбинаций дает также разрешенную комбинацию. |
|
Пусть |
комбинации |
v(aia2 |
. • • ак, |
Ьф2 |
• • • br) |
и |
v'(a'ia'2... |
а'и, Ь'ф'2... |
b'r) |
являются |
'разрешенными ком |
бинациями систематического |
(п, /г)-кода |
(а и b — инфор |
мационные и проверочные элементы соответственно). Со гласно определению каждый проверочный элемент об разуется посредством линейных операций над информа ционным, т. е. путем сложения по модулю 2 определен ных информационных разрядов:
h = |
С 1 а ! © с 2 0 2 © ... @ckak |
( 6 , 2 1 ) |
b\ = |
|
с1а[©с2а2®...®сГ1а'к ) |
|
|
где Cj. сг, • •., c/t |
— |
числа, равные 0 или 1. |
|
Под сложением |
двух n-элементных кодовых комбина |
ций понимается операция, в результате которой новая комбинация 'формируется путем сложения одноименных разрядов. В нашем случае сумма по модулю 2 двух раз решенных комбинаций будет иметь вид
v©v' |
= (ai.@a[); |
( a a © f l Q ; . . . ; |
(ak@ak); |
|
(bi@b[); |
( 6 8 |
< Щ ) ; . . . ; (br |
+ b'r). |
Из выражения |
(6.21) |
следует |
|
bi © b\ = |
d (ах © а]) + |
с2 (а2 + а'_) © |
... © c k (ak © a'k). |
Нетрудно видеть, что проверочные разряды кодовой комбинации, полученной суммированием по модулю 2 двух разрешенных комбинаций, образуются по тому ж е правилу, что и для каждой разрешенной комбинации. Следовательно, сумма двух разрешенных комбинаций систематического кода также является разрешенной ком бинацией. Это положение справедливо и при суммирова нии по модулю 2 любого количества разрешенных ком бинаций систематического кода ' ) .
Вторым свойством систематических (п, k)-кодов, вы текающим из рассмотренного выше, является то, что ми нимальное кодовое расстояние таких кодов равно мини мальному весу его ненулевых кодовых комбинаций. Спра ведливость сказанного вытекает из следующего: 1) вес кодовой комбинации w определяется числом ненулевых
|
|
|
|
элементов в ней, т. е. числом |
единиц; 2) кодовое расстоя |
ние d между |
комбинациями |
и,- и Vj определяется весом |
комбинации |
w(vu), полученной сложением |
по модулю 2 |
(Сравниваемых комбинаций Vk = и,-© vy, 3) |
поскольку ко |
довая комбинация Vk является также и разрешенной ком бинацией рассматриваемого кода, то минимальное ко довое расстояние кода определяется минимальным ве сом его ненулевых кодовых комбинаций. Последнее свой-
J ) В любом систематическом коде нулевая комбинация, т. е. комбинация, состоящая из одних нулей, принадлежит к числу раз решенных, поскольку линейная комбинация нулей есть нуль.
ство очень важно, так как оно значительно упрощает определение корректирующих возможностей кода. Ис пользуя это свойство, можно попытаться задать весь си стематический (п, /ej-код, приводя не все его кодовые комбинации, а только лишь их часть, указав при этом способ, посредством которого однозначно определяются все остальные комбинации.
Покажем, что для формирования систематического (п, &)-кода, содержащего 2к разрешенных кодовых ком бинаций, достаточно иметь К линейно независимых ком
бинаций. Совокупность комбинаций Ь\; и2 ; |
.. .; u;t назы |
вается линейно независимой, если для всех |
возможных |
значений |
с,, за исключением Ci = c 2 |
= . . . |
=Ch = 0, 'соб |
людается |
неравенство1 ) C\V\ @c2V2@ |
. ..® |
СьРиФ®. Вы |
бирая все возможные |
наборы |
значений элементов с\, чи |
сло которых |
равно |
2к, |
получим 2к кодовых комбинаций, |
причем при |
C i = c2 |
= ... = Cft = 0 |
получим нулевую комбина |
цию, которая также является |
разрешенной. |
Таким образом, любой набор из К линейно независи мых кодовых комбинаций порождает (п, ^-систематиче ский код. Обычно такой набор кодовых комбинаций принято записывать друг под другом в виде матрицы, содержащей /г строк и п столбцов. Такая матрица назы вается порождающей матрицей (п, /cj-кода и обозна чается символом С-( П | ;,). Так как информационные раз ряды занимают обычно первые К позиций в кодовых ком бинациях, то порождающую матрицу, содержащую К линейно независимых комбинаций, целесообразно пред ставить состоящей из единичной матрицы kXk, полно стью характеризующей комбинации простого кода:
• 100 . . . о 010 . . . о 001 . . . о
000. . . 1
иприписанной к ней справа матрицы проверочных эле ментов, содержащей К строк и г столбцов:
"10 . . . 0 ЬЦЬЦ . . , Ь 1 Г
101 . . . 0 |
621622 |
. . , Ь2г |
'in. к) |
|
|
(6.22) |
|
|
|
00 |
1 |
Л1ьЬ1иь,к1 |
|
|
|
•) Элементы толя ct , с2 , .... ск могут |
принимать значение 0 или 1. |
Порождающая матрица вида (6.22) называется ка нонической и сокращенно записывается в форме
|
<?(в. л, = [hR{n_k) |
J . |
|
(6.23) |
где /л — |
единичная |
матрица |
размерности |
(kXk), |
R(n-k)xk — |
матрица |
размерности |
(п—k)Xk, |
составлен |
ная из п—k проверочных элементов базисных кодовых комбинации.
При определении значений проверочных элементов приписанной части матрицы следует исходить из основ ных свойств систематических кодов.
Поскольку каждая строка единичной матрицы kXk содержит одну единицу, то вес каждой строки припи
санной части матрицы не должен |
быть меньше d — 1 , а |
сумма по модулю 2 двух любых |
ее строк — не менее |
d—2 единиц. iB общам случае комби-нации приписанной части матрицы находят, перебирая различные комбина ции, содержащие не менее d—1 единиц. Построенные та ким образом К исходных я-элементных комбинаций (п, /г)-кода должны быть линейнонезависимыми.
Процесс кодирования в систематическом коде сводит ся к определению проверочных разрядов посредством линейных операций над К информационными разряда ми. Для этого необходимо составить г независимых сумм по модулю 2.
Выбор позиций 1 к 0 в приписанной части матрицы (6.22) однозначно определяет позиции тех информаци онных элементов, которые должны участвовать в обра зовании проверочных разрядов. Ответ на этот вопрос
|
|
|
|
легко |
получить, если построить проверочную матрицу |
М(П-к), |
имеющую г строк и п столбцов. Для этого к еди |
ничной |
матрице гХг слева |
приписывается, матрица, со |
держащая |
К столбцов и г строк, причем каждая ее стро |
ка должна |
соответствовать |
столбцу проверочных раз |
рядов порождающей матрицы (6.22):
|
ЬцЬп |
. . . |
6 И |
Ю . . . О |
|
м (п, k) |
Ь1гЫл |
. . . Ькг 01 . . . о |
(6.24) |
|
|
|
|
|
|
\birb2r |
. |
bkr |
00 |
1 |
|
Каноническая |
форма |
матрицы |
М(п, к) имеет |
вид |
Min,h)=[R'kx{n+k)f{n-k)]- |
С |
помощью |
матрицы (6.24) |
опе- |
