Лекция 24
БЛОЧНЫЕ ЛИНЕЙНЫЕ КОДЫ
24.1 Математическое описание процессов кодирования и декодирования
24.2 Коды с проверкой на четность
24.3 Коды Хэмминга
24.4 Коды с постоянным весом
24.1 Математическое описание процессов кодирования и декодирования
Линейным блочным
(
)
m
n
,
- кодом называется множество
N
последовательностей длины
n
над
(
)
g
GF
, называемых
кодовыми словами, которое характеризуется тем, что сумма двух кодовых слов является кодовым словом, а произведение
любого кодового слова на элемент поля также является кодовым словом.
Поле
(
)
g
GF
, состоящее из конечного числа элементов
g
называется конечным полем
или полем Галуа. Для любого числа
g
, являющегося степенью простого числа, существует поле, насчитывающее
g
элементов. Поле не может содержать менее
двух элементов, поскольку в нем должны быть по крайней мере единичный элемент относительно операции сложения (0) и
единичный элемент относительно операции умножения (1). Поле, включающее только 0 и 1, обозначим GF(2). Правила
сложения и умножения в поле с двумя элементами следующие:
+
0
1
х
0
1
0
0
1
0
0
0
1
1
0
1
0
1
Двоичные кодовые комбинации, являющиеся упорядоченными последовательностями из
n
элементов поля
(
)
2
GF
,
рассматриваются в теории кодирования как частный случай последовательностей из
n
элементов поля
(
)
x
GF
.
Обычно
m
q
N
=
, где
m
- некоторое целое число. Если
2
=
q
, линейные коды называются групповыми, так как кодовые
слова образуют математическую структуру, называемую группой. При формировании этого кода линейной операцией является
суммирование по mod2.
При задании кода обычно указывают, какие информационные элементы принимают участие в формировании каждого из
k
проверочных разрядов. Например, для кода с
n
=5,
m
=3 и
k
=2 каждый проверочный разряд
i
b
определяется суммированием
по модулю 2 по правилу
2
1
1
a
a
b
Е
=
;
3
2
2
a
a
b
Е
=
где
i
a
- информационные разряды. Комбинация такого кода записывается в виде
2
1
3
2
1
,
,
,
,
b
b
a
a
a
или в обратном
1
2
3
1
2
,
,
,
,
a
a
a
b
b
. При задании кода можно указать все разрешенные для этого кода комбинации. Для линейных кодов способ
задания можно значительно упростить. Для
m
информационных разрядов число всех разрешенных кодовых комбинаций будет
равняться
m
2
.
Пусть
3
=
m
. Так как в каждой кодовой комбинации такого кода три информационных элемента, то число возможных
комбинаций кода будет равно
8
2
2
3
=
=
m
, а именно:
Таблица 24.1
№ п/п
а
1
а
2
а
3
b
1
b
2
1
2
3
4
5
6
7
8
1
0
0
1
0
1
1
0
0
1
0
1
I
0
1
0
0
0
1
0
I
1
1
0
1
1
0
0
I
1
0
0
0
1
1
1
0
1
0
0
Комбинация из одних нулей не используется, поэтому число разрешенных комбинаций в таком коде равно
7
1
2
1
2
3
=
-
=
-
=
m
m
N
.
Проверочные элементы формируются как сумма по модулю два информационных элементов, а именно:
о
н
м
Е
=
Е
=
.
,
3
2
2
2
1
1
а
а
b
а
а
b
(24.1)
Так для кодовой комбинации №4
,
1
0
1
,
0
1
1
3
2
2
2
1
1
=
+
=
Е
=
=
+
=
Е
=
а
а
b
а
а
b
в соответствии с правилами суммирования по модулю 2. Знак означает суммирование по модулю.
Минимальный вес
min
W
кодовой комбинации представляет число разрядов, в которых элементы являются единичными. Для
рассматриваемого кода
min
W
=2
. То есть каждая кодовая комбинация содержит не менее двух единиц.
Для задания кода нет необходимости записывать в таблицу все используемые комбинации данного кода. Код может быть задан
матрицей, которая содержит один из возможных наборов линейно независимых строк. (Напомним, линейно независимыми
называют такие строки, любая комбинация суммирования которых по модулю 2 не дает нулевых комбинаций).
Выберем из всех кодовых комбинаций только линейно независимые. Под линейно независимыми кодовыми комбинациями
понимают такие, сумма по модулю 2 которых (в любом сочетании) не равняется нулю. Так для приведенного выше кода
линейно независимыми будут группы комбинаций:
1. 1 0 0 1 0
2. 0 1 0 1 1
3. 0 0 1 0 1
1. 1 0 0 1 0
4. 1 1 0 0 1
5. 0 1 1 1 0
1. 1 0 0 1 0
4. 1 1 0 0 1
7. 1 1 1 0 0
(1)
(2)
(3)
Можно выбрать и другие группы линейно независимых комбинаций этого кода. Путем поэлементного сложения по модулю 2
любого сочетания из приведенных выше в группах комбинаций не удается получить нулевой комбинации. Для первой группы:
1) 1 0 0 1 0
Е
2) 0 1 0 1 1
--------------------
1 1 0 0 1
1) 1 0 0 1 0
Е
3) 0 0 1 0 1
------------------
1 0 1 1 1
2) 0 1 0 1 1
Е
3) 0 0 1 0 1
--------------------
0 1 1 1 0
1) 1 0 0 1 0
Е
2) 0 1 0 1 1
Е
3) 0 0 1 0 1
-------------
1 1 1 0 0.
(4)
(5)
(6)
(7)
Обычно линейно независимые кодовые комбинации записывают в виде матрицы размером
m
n
ґ
, которая называется
порождающей и обозначается
)
,
(
m
n
G
. Чаще всего порождающие матрицы записывают в так называемой каноничной форме.
При этом первые или последние
m
столбцов этой матрицы образуют единичную матрицу.
Таким образом, любая из трех приведенных выше комбинаций может быть порождающей для систематического (5, 3) кода с
d=2.
В общем виде производящую матрицу из
m
строк и
n
– столбцов записывают так:
mn
2
mm
1
mm
mm
m2
m1
2n
2
2m
1
2m
2m
22
21
1n
2
1m
1
1m
1m
12
11
b
...
b
b
a
...
a
a
.
...
.
.
...
.
.
.
...
.
.
...
.
.
.
...
.
.
.
...
.
.
b
...
b
b
a
...
a
a
b
...
b
b
a
...
a
a
m
n
G
+
+
+
+
+
+
=
.
.
)
,
(
.
(24.2)
Здесь первые
m
столбцов являются информационными и последние
m
n
-
столбцов – проверочными. Производящую
матрицу
(
)
m
n
,
обычно записывают в канонической форме
m
k
m
I
R
m
n
G
Ч
=
ґ
)
,
(
или
k
m
m
R
I
m
n
G
ґ
Ч
=
)
,
(
.
(24.3)
где
m
n
k
-
=
–
число проверочных элементов,
m
I
- матрица информационных элементов, представляет собой единичную
матрицу размерности
m
m
ґ
, т.е. квадратная матрица, у которой единицы находятся только на главной диагонали,
k
m
R
,
-
матрица проверочных элементов, размерность которой
k
m
ґ
.
Для рассматриваемого примера – (5,3) кода каноническая форма порождающей матрицы имеет вид
Из данного примера видно, что первые три столбца составляют единичную матрицу; четвертый столбец указывает, что при
формировании первого проверочного разряда принимают участие первый и второй информационные разряды. Пятый столбец
указывает, что при формировании второго проверочного разряда принимают участие второй и третий информационные разряды.
Для
)
3
,
5
(
G
1
0
0
0
1
0
0
0
1
=
m
I
. (24.4)
Затем выделяется подматрица
T
mxk
R
являющаяся транспонированной матрицей
mxk
R
:
если
1
0
1
1
0
1
=
mxk
R
то
1
1
0
0
1
1
=
T
mxk
R
. (24.5)
Затем полученной матрице
T
mxk
R
справа приписывается единичная матрица и получается проверочная матрица
Н
.
1
0
0
1
1
1
0
0
1
1
=
H
. (24.6)
Кодовые комбинации кода должны содержать
2
3
5
=
-
=
-
=
m
n
k
проверочных символа. Подматрица
T
mxk
R
указывает
на то, что проверочные символы должны определяться равенствами:
о
н
м
Е
=
Е
=
3
2
2
2
1
1
а
а
b
а
а
b
.
Тогда для сообщения, представляемого простой кодовой комбинацией 010 проверочные символы будут
1
1
0
1
=
Е
=
b
и
1
0
1
2
=
Е
=
b
. Следовательно, полная кодовая комбинация будет иметь вид: 01011.
Проверочная матрица очень удобна для определения места ошибки в кодовой комбинации, а следовательно и исправления
ошибки.
Проверочная матрица однозначно связана с порождающей соотношением
0
)
,
(
=
T
H
m
n
G
, (24.7)
Где умножение и суммирование соответствующих элементов матриц производится по модулю 2. Напомним, что умножение по
модулю 2 представляется в виде
0
0
0
=
Д
,
0
0
1
1
0
=
Д
=
Д
,
1
1
1
=
Д
.
Пример.
Для порождающей матрицы, G(5,3) проверочная матрица имеет вид
m
T
k
m
I
R
H
ґ
=
=
1
0
0
1
1
1
0
0
1
1
Тогда
.
0
0
0
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
1
0
1
0
0
1
0
0
1
)
3
,
5
(
=
ґ
=
T
H
G
Допустим, что переданная кодовая комбинация записана в виде вектора
4
3
4
2
1
4
3
4
2
1
разряды
е
Проверочны
k
разряды
нные
Информацио
m
b
b
b
a
a
a
F
...
...
2
1
2
1
=
(24.8)
Процесс декодирования математически описывают произведением проверочной матрицы
H
и вектора – столбца,
отображающего принятую кодовую комбинацию
E
F
F
+
=
'
, где
E
- вектор ошибки
(24.9)
где
– результат декодирования (синдром);
T
)
(
·
- знак транспортирования.
В теории кодирования синдром, который также называют опознавателем ошибки, обозначает совокупность признаков,
характерных для определённой ошибки. Для исправления ошибки на стороне приёма необходимо знать не только факт её
существования, но и её местонахождение, которое определяется по установленному виду вектора ошибки
.
Поскольку связь между порождающей и проверочной матрицами, определяется равенством
0
)
,
(
)
,
(
=
=
m
n
HG
H
m
n
G
T
,
то получим
T
T
EH
HE
S
=
=
. (24.10)
Если обозначить
i
h
i
- й столбец проверочной матрицы, то
n
T
h
h
h
H
i
...
2
1
=
.
Вектор ошибки
000
...
1
...
00
=
E
содержит «1» на тех позициях, символы на которых искажены. Пусть эти позиции имеют
номера
l
V
V
V
,...,
,
2
1
, тогда будет справедливо равенство
е
=
=
=
l
i
v
T
h
EH
S
1
. (24.11)
Следовательно, если необходимо обнаружить
l
ошибок, то должно быть выполнено условие
0
1
№
е
=
l
i
v
h
,
при любом сочетании
l
искаженных символов.
Если же необходимо исправить
l
ошибок, то сумма по модулю 2 для любого
l
конкретных столбцов проверочной матрицы
должна быть вполне определенной, которая не совпадает с аналогичной суммой для других
l
столбцов. Так, например, при
исправлении одиночной ошибки все столбцы проверочной матрицы должны быть разными, то есть
j
i
h
h
№
при любых
i
и
j
;
j
i
№
. Если же необходимо исправить одиночную ошибку и обнаружить пакет, состоящий из трех или двух ошибок, то
необходимо выполнить следующие условия:
j
i
h
h
№
при
j
i
№
(для исправления одиночной ошибки);
j
i
i
i
i
h
h
h
h
h
№
+
№
+
+
+
1
1
;
0
при любых
i
и
j
(для обнаружения пакета из двух ошибок);
j
i
i
i
i
i
i
h
h
h
h
h
h
h
№
+
+
№
+
+
+
+
+
+
2
1
2
1
;
0
при любых
i
и
j
(для обнаружения пакета из трех ошибок).
Матрицы
H
и
)
,
(
m
n
G
можно поменять ролями. Тогда матрица
H
будет порождающей, а
)
,
(
m
n
G
- проверочной.
Коды, взаимосвязанные между собой таким образом, называют дуэльными (двойственными).
24.2 Коды с проверкой на четность
При построении таких кодов передаваемая последовательность разрядов разбивается на группы. В наиболее простом случае
проверка на четность производится в каждой группе, в результате чего число единиц в группе доводится до четного.
В таком коде к кодовым комбинациям безизбыточного первичного двоичного
m
-разрядного кода добавляется один
дополнительный разряд (символ проверки на четность, называемый проверочным, или контрольным). Если число символов 1
исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ 0, а если число символов
1 нечетное, то в дополнительном разряде формируют символ 1. В результате общее число символов 1 в любой передаваемой
кодовой комбинации всегда будет четным.
Таким образом, правило формирования проверочного символа сводится к следующему:
m
a
a
a
b
Е
Е
Е
=
...
2
1
. (24.12)
где
a
— соответствующий информационный символ (0 или 1),
т
— общее их число.
Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с
числом комбинаций исходного первичного кода, а условие четности разделяет все комбинации на разрешенные и
неразрешенные. Код с проверкой на четность позволяет обнаруживать одиночную ошибку при приеме кодовой комбинации,
поскольку такая ошибка нарушает условие четности, переводя разрешенную комбинацию в запрещенную.
Критерием правильности принятой комбинации является равенство нулю результата
S
суммирования по модулю 2 всех
п
символов кода, включая проверочный символ
.
При наличии одиночной ошибки
принимает значение 1 :
(24.13)
Этот код является
)
,
1
(
m
m
+
-кодом, или
)
1
,
(
-
n
n
-кодом. Минимальное расстояние кода равно двум
2
min
=
d
, и,
следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на четность может использоваться только
для обнаружения (но не исправления) однократных ошибок.
Проверочная матрица кода с проверкой на четность имеет вид
1
...
1111
=
H
. (24.14)
Основным недостатком кода является необнаружение ошибок четной кратности. Поэтому такие коды находят применение в тех
звеньях систем передачи, где наиболее вероятны одиночные ошибки.
Ошибки же, возникающие в канале связи, имеют тенденцию к группированию. Для устранения этого недостатка группы
разрядов (кодовые комбинации) записываются в виде матрицы. Затем производится проверка на четность столбцов полученной
матрицы.
При наличии одной групповой ошибки длиной не более числа элементов в строке матрицы в каждую проверку будет входить не
более одного искаженного разряда (произойдет декорреляция ошибок). Ошибки не будут обнаружены, если искажено четное
число разрядов в столбце.
Если ошибки независимы, то данный код эквивалентен коду с проверкой на четность по строкам. Если же ошибки
коррелированы, то за счет проверки разнесенных разрядов (за счет декорреляции ошибок) данный код будет более
помехоустойчивым.
Для повышения обнаруживающей способности проверка на четность может быть проведена одновременно по строкам и
столбцам. Последний код называют итеративным (иногда матричным). В данном коде проверочные разряды формируются по
следующим правилам:
1
2
1
2
1
2
2
22
21
1
1
12
11
...
...
...
...
...
...
...
...
...
+
m
m
l
lm
l
l
m
m
c
c
c
c
b
a
a
a
b
a
a
a
b
a
a
a
(24.15)
l
m
m
m
lj
j
j
j
im
i
i
i
b
b
b
с
или
c
c
c
c
a
a
a
c
a
a
a
b
Е
Е
Е
=
Е
Е
Е
=
Е
Е
Е
=
Е
Е
Е
=
+
+
...
;
...
;
...
;
...
2
1
1
2
1
1
2
1
2
1
(24.16)
При таком построении кода будут обнаружены все одиночные, двойные и тройные ошибки, а также все нечетные ошибки, и
некоторые четные ошибки большей кратности.
Если пренебречь ошибками кратности более четвёртой, то можно показать, что вероятность необнаруженной ошибки будет
равна
4
)
1
)(
1
(
4
2
1
2
1
)
1
(
-
+
+
+
+
-
=
l
m
ош
ош
l
m
HO
p
p
C
C
P
. (24.17)
Иногда при построении кода строят квадратную матрицу, т. е. принимают
l
m
=
. При этом обеспечивается наименьшая
избыточность.
Итеративные коды могут использоваться в сочетании с другими кодами. При этом каждая строка матрицы является
разрешенной комбинацией какого-либо кода. В этом случае говорят о произведении двух кодов. Произведение кодов
используется и для исправления ошибок.
Данный способ кодирования реализует один из методов так называемого, перемеживания, обеспечивающего эффективную
борьбу с групповыми ошибками.
В ряде случаев при построении обнаруживающих кодов элементы кодовой комбинации подвергаются многократной проверке на
чётность. Каждая такая проверка охватывает вполне определённые позиции. Часть из этих позиций может входить и в другие
проверки. Число проверок и номера позиций, входящих в каждую проверку, выбираются так, чтобы при данной избыточности
обеспечить наибольшее расстояние между кодовыми комбинациями.
Известно, что
min
d
на единицу больше минимального числа проверок, в которые входит символ. Поэтому для увеличения
помехоустойчивости стремятся каждую позицию охватить максимальным числом проверок. Такие коды в большинстве случаев
строятся методом подбора.
Увеличивая число дополнительных проверочных разрядов и формируя по определенным правилам проверочные символы
b
,
равные 0 или 1, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять
ошибки. На этом и основано построение кодов Хэмминга.
24.3 Коды Хэмминга
Коды Хэмминга
позволяют исправлять одиночную ошибку с помощью непосредственного описания. Для каждого числа
проверочных символов
существует классический код Хэмминга с маркировкой
)
1
2
,
1
2
(
)
,
(
k
m
n
k
k
-
-
-
=
,
(24,18)
т.е. — (7,4), (15, 11), (31, 26) ...
При других значениях числа информационных символов
т
получаются так называемые
усеченные
(или
укороченные) коды
Хэмминга.
Так, для международного телеграфного кода МТК-2, имеющего 5 информационных символов, потребуется
использование корректирующего кода (9,5), являющегося усеченным от классического кода Хэмминга (15,11), так как число
символов в этом коде уменьшается (укорачивается) на 6. Для примера рассмотрим код Хэмминга (7,4).
В простейшем варианте при заданных четырех
(т=
4) информационных символах
)
,
,
,
(
4
3
2
1
a
a
a
a
будем полагать, что они
сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя
проверочными символами (
3
=
k
), задавая их следующими равенствами проверки на четность, которые определяются
соответствующими алгоритмами. Известно, что кодовое расстояние равно минимальному числу проверок, в которые входит
информационный символ, плюс 1. В рассматриваемом коде
3
min
=
d
.
Следовательно, каждый информационный символ
должен входить минимум в две проверки. Определим правило формирования проверочных символов следующим образом:
.
;
;
4
2
1
3
4
3
2
2
3
2
1
1
a
a
a
b
a
a
a
b
a
a
a
b
Е
Е
=
Е
Е
=
Е
Е
=
(24.20)
В соответствии с этим алгоритмом определения значений проверочных символов
b
в табл. 24.2 приведены все возможные 16
кодовых слов кода Хэмминга (7,4).
Таблица 24.2
4
=
m
3
=
k
1
a
2
a
3
a
4
a
1
b
2
b
3
b
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
1
1
1
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
0
1
1
0
0
1
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
1
1
0
0
0
1
0
1
1
0
1
0
0
1
1
1
1
0
1
0
0
1
1
1
1
1
1
1
Составим производящую матрицу
(
)
4
,
7
в канонической форме
4
3
4
)
4
,
7
(
I
R
G
Ч
=
ґ
или
3
4
4
)
4
,
7
(
ґ
Ч
=
R
I
G
.
Таблица 24.3
1
a
2
a
3
a
4
a
1
b
2
b
3
b
9
1
0
0
0
1
0
1
5
0
1
0
0
1
1
1
3
0
0
1
0
1
1
0
2
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
0
1
3
4
=
ґ
R
,
1
0
1
1
1
1
1
0
0
1
1
1
3
4
=
ґ
T
R
Составим проверочную матрицу
1
0
0
1
0
1
1
0
1
0
1
1
1
0
0
0
1
0
1
1
1
=
H
.
Транспонированная проверочная матрица будет иметь вид
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
1
1
1
0
1
=
T
H
.
Предположим, что на вход декодера для (7,4)-кода Хэмминга поступает кодовое слово
(
)
'
3
'
2
'
1
'
4
'
3
'
2
'
1
'
b
b
b
a
a
a
a
F
=
.
Апостроф означает, что любой символ слова может быть искажен помехой в канале связи и возникает ошибка
E
.
В декодере в режиме исправления ошибок строится последовательность:
T
T
E
F
H
HF
S
)
(
'
+
=
=
(24.21)
где
S
– результат декодирования (синдром), который в данном случае является трехсимвольным.
Символы синдрома можно так же получить с использованием следующей процедуры
.
;
;
4
2
1
3
3
4
3
2
2
2
3
2
1
1
1
a
a
a
b
s
a
a
a
b
s
a
a
a
b
s
Е
Е
Е
=
Е
Е
Е
=
Е
Е
Е
=
(24.22)
В данном случае синдром
(
)
3
2
1
,
,
s
s
s
S
=
представляет собой сочетание результатов проверки на четность соответствующих
символов кодовой группы и характеризует определенную конфигурацию ошибок
(вектор ошибок).
Число возможных синдромов определяется выражением
k
S
2
=
.
(24.23)
При числе проверочных символов
3
=
k
имеется восемь возможных синдромов (23 = 8). Нулевой синдром (000) указывает на
то, что ошибки при приеме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определенная
конфигурация ошибок, которая и исправляется. Классические коды Хэмминга (24.18) имеют число синдромов, точно равное их
необходимому числу, позволяют исправить все однократные ошибки в любом информативном и проверочном символах и
включают один нулевой синдром. Такие коды называются плотноупакованными
.
Усеченные коды являются
неплотно упакованными,
так как число синдромов у них превышает необходимое. Так, в коде (9,5)
при четырех проверочных символах число синдромов будет равно 24 =16, в то время как необходимо всего 10. Лишние 6
синдромов свидетельствуют о неполной упаковке кода (9,5).
Для рассматриваемого кода (7,4) в табл. 24.4 представлены ненулевые синдромы и соответствующие конфигурации ошибок.
Таблица 24.4
Синдром
001
010
011
100
101
110
111
Конфи-гураци
я ошибок
0000001
0000010
0001000
0000100
1000000
0010000
0100000
Ошиб-
ка в символе
3
b
2
b
4
a
1
b
1
a
3
a
2
a
Таким образом, код (7,4) позволяет исправить все одиночные ошибки. Простая проверка показывает, что каждая из ошибок
имеет свой единственный синдром. При этом возможно создание такого цифрового корректора ошибок (дешифратора
синдрома), который по соответствующему синдрому исправляет соответствующий символ в принятой кодовой группе. После
внесения исправления проверочные символы
, можно на выход декодера не выводить. Две или более ошибки превышают
возможности корректирующего кода Хэмминга, и декодер будет ошибаться. Это означает, что он будет вносить неправильные
исправления и выдавать искаженные информационные символы.
Идея построения подобного корректирующего кода, естественно, не меняется при перестановке позиций символов в кодовых
словах. Все такие варианты также называются кодами Хэмминга (7,4).
Расширенные коды Хэмминга
получают в результате дополнения кодов с
3
min
=
d
общей проверкой каждой из кодовых
комбинаций на четность, т.е. еще одним проверочным символом. Это позволяет увеличить минимальное кодовое расстояние
до
4
min
=
d
.
За показатель помехоустойчивости кода Хэмминга примем вероятность приёма кодовой комбинации с ошибками.
Расчёт вероятности ошибки произведём для семиэлементного кода, считая искажения символов в кодовых комбинациях
равновероятными и независимыми.
Приём с ошибкой при применении кода Хемминга с исправлением одиночной ошибки будет в том случае, если искажено более
одного символа. В соответствии с этим вероятность искажения кодовой комбинации равна
6
0
0
7
0
)
1
(
7
)
1
(
1
p
p
p
P
ош
-
-
-
-
=
, (24.24)
где
7
0
)
1
(
p
-
- вероятность отсутствия искажений;
6
0
0
)
1
(
7
p
p
-
- вероятность возникновения одной ошибки.
24.4 Коды с постоянным весом.
Под кодом с постоянным весом понимают двоичный равномерный код, в котором все разрешенные комбинации содержат
одинаковое число единиц. Такой код обеспечивает обнаружение всех ошибок за исключением тех случаев, когда несколько
единиц превратятся в нули, а столько же нулей – в единицы. Эти ошибки называют ошибками смещения.
Основным достоинством этих кодов является их высокая помехоустойчивость в ассиметричных каналах. Недостаток состоит в
том, что из-за отсутствия чёткого разделения на информационные и проверочные символы для кодирования и декодирования
необходимы достаточно сложные кодопреобразователи.
В настоящее время широкое распространение получили коды «2 из 5», «3 из 6», «3 из 7», «4 из 8 «, «3 из 8».
В семиэлементном коде (коде «3 из 7») количество кодовых комбинаций с соотношением единиц и нулей 3:4 равно 35.
При независимых ошибках это выражение будет иметь вид
i
i
i
i
i
ош
p
p
C
C
P
2
7
2
3
3
1
4
)
1
(
-
=
-
=
е
.
Биимпульсный (код Манчестера) является кодом с постоянным весом как в пределах кодовой комбинации, так и в пределах
длительности одной информационной посылки.
Кодирование заключается в том, что информация о нуле и единице заключена в двух импульсах противоположной полярности и
с определённой последовательностью смены полярности. Например, при передаче «единицы» первый из двух импульсов
положительный, а второй – отрицательный. При передаче «нуля» первый импульс отрицательный, а второй положительный
(рис.24.1).
1
0
1
1
1
1
0
1
U1
U2
t
Рис.24.1 Биимпульсный код
Применение такого кода позволяет улучшить решение задачи тактовой синхронизации приёмной аппаратуры. Поэтому он
находит широкое применение в высокочастотных цифровых системах передачи. Кроме этого биимпульсный код позволяет
обнаружить возникающие ошибки.
Нарушение последовательности смены полярности импульсов может быть вызвано появлением ложного импульса. Это будет
свидетельствовать о наличии ошибки в кодовой комбинации. Ошибка не обнаруживается только в том случае, когда в одной
паре импульсов, соответствующих данной информационной посылке, искажались оба символа. Следовательно, если ошибки
взаимонезависимы, то вероятность необнаруженной ошибки будет равна
i
m
i
m
i
i
m
ош
p
p
C
P
2
'
2
2
1
)
1
(
-
=
-
=
е
, (24.25)
где
–число посылок в кодовой комбинации до получения биимпульсной последовательности.
С целью повышения помехоустойчивости биимпульсный код сочетается с другим кодом, например с кодом проверки на
чётность. В этом случае в комбинации с чётным числом единиц формируют биимпульсный код. Тогда ошибка не будет
обнаружена только при искажении четного числа биимпульсных посылок. Вероятность этого события при независимых ошибках
будет равна
i
n
i
m
i
i
m
ош
p
p
C
P
2
'
2
2
...
6
,
4
,
2
)
1
(
-
=
-
=
е
, (24.26)
где
1
'
'
+
=
m
n
- число символов в кодовой комбинации с проверкой на четность. Недостатками биимпульсного кода являются:
- большая избыточность
5
,
0
»
r
;
- сложность кодопреобразователей.
