Файл: Основы бортовых вычислительных машин.pdf

239
(избыточных) символов, связанных определенной зависимостью с символами информационной последовательности. В явном виде они в передаваемое сообщение не входят, а могут быть установлены по из- вестным зависимостям, связывающим их с символами передаваемого сообщения.
По способу кодирования различают блочные и непрерывные ко- ды. При блочном кодировании информационная последовательность разбивается на блоки символов
(
)
1 2
,
,...,
k
b b
b
фиксированной длины
k
, каждому из которых ставится в соответствие определенная комби- нация символов алфавита канала
(
)
1 2
,
,...,
n
β β
β
, называемого кодо- вым словом. Код при блочном кодировании определяет закон форми- рования кодового слова, отвечающего данному блоку информацион- ных символов.
В случае систематического блочного кода кодовое слово, отве- чающее блоку информационных символов
(
)
1 2
,
,...,
k
b b
b
, может быть представлено в виде
(
)
1 2
1
,
,...,
,
,
,...,
k
k
k
n
b b
b
β β
β
+
, где
1
,...,
k
n
β
β
+
- из- быточные символы. Блочный код, приводящий в соответствие блоку информационных символов длиной
k
кодовое слово длиной n , будем обозначать
( )
,
k n
. Избыточные символы не несут дополнительной информации об источнике сообщения (они однозначно определяются информационными символами
1 2
,
,...,
k
b b
b ), Поэтому кодовое слово несет то же количество полезной информации, что и соответствую- щий блок информационных символов. При безызбыточности входно- го сообщения блок из k информационных символов (а значит, и ко- довое слово) несет количество информации
2
log
Н
k
m
=
, где m - объем алфавита источника.
Максимальное количество информации, которое может содер- жать слово из n символов канала при том же объеме алфавита m , равно max
2
log
Н
n
m
=
Поэтому избыточность кода
( )
,
k n
2
max
2
log
1 1
log
и
k
m
Н
n k
r
Н
n
m
n
n
ρ
−
= −
= −
=
=
, где
r
n k
= −
- число избыточных символов, вносимых при кодирова- нии.
При непрерывном кодировании каждый символ передаваемого сообщения определяется рекуррентными соотношениями,

240 связывающими его с соответствующими символами информационной последовательности:
1
,
(mod ),
0,1,...,
1
S
i j
j i
q
C b
m
j
l
ν
ν
ν
β
=
+
=−




=
=
−




∑
(6.4)
Значение правой части выражения (6.4) определяется по моду- лю m для того, чтобы полученные значения символов
,
i j
β
принадле- жали алфавиту канала, т.е. принимали одно из значений
0, 1, ..., m -1.
Соотношение (6.1) на i - м шаге кодирования группе символов входной последовательности
1
,..., ,...,
i q
i
i s
b
b
b
−
+ −
ставит в соответствие
l
символов кодовой последовательности
,0
, 1
,...,
i
i l
β
β
−
; на (
i
+1)- m шаге группе символов
1 1
,...,
,...,
i q
i
i s
b
b
b
− +
+
+
, смещенной на одну пози- цию, ставит в соответствие следующие
l
символов кодовой последо- вательности
1,0 1, 1
,...,
i
i
l
β
β
+
+ −
и т.д. Таким образом, на каждый символ информационной последовательности приходится
l
символов пере- даваемой кодовой последовательности, что соответствует избыточно- сти кода
( )
1 /
и
l
l
ρ
= −
. Правая часть соотношения (6.4) представляет как бы свертку соответствующего участка информационной последо- вательности, поэтому коды и называют сверточными.
Непрерывные (сверточные) коды могут быть как систематиче- скими, так и несистематическими. Систематические сверточные коды получаются в частном случае, когда для одного из значений индекса
j
(например,
j
= 0) коэффициенты в формуле (6.4) принимают значе- ния
0 0, при
0,
1, при
0
C
ν
ν
ν
≠

=

=

и соответственно
0
i
i
b
β
=
. В этом случае передаваемая последова- тельность имеет вид
,1
, 1 1
1,1 1, 1
... ,
,...,
,
,
,...,
,...
i
i
i l
i
i
i
l
b
b
β
β
β
β
−
+
+
+ +
6.3.2 Коды, контролирующие ошибки
Одним из наиболее широко распространенных способов контро- ля передачи, хранения и обработки цифровой информации, в том чис- ле и в бортовых ЭВМ, является контроль по модулю. При контроле

241 по модулю используется избыточная информация, представляемая дополнительными разрядами в информационном слове. Количество дополнительных разрядов определяется значением модуля, по кото- рому производится контроль.
Суть метода заключается в определении и анализе по некоторым правилам контрольных кодов, представляющих собой наименьшие остатки от деления на модуль самих чисел (числовой контроль) или суммы их цифр (цифровой контроль).
В первом случае контрольные разряды определяются из соот- ношения:
m
х
ост
m
α
=
, где x - контролируемое число;
m
α
- наименьший остаток от деления числа x на модуль m .
Например, при контроле по модулю 2 для числа x = 1001 полу- чаем
2 1001 1
10
ост
α
=
=
В этом случае избыточный код имеет значение
2
х
=
1001 1 контрольный разряд.
Очевидно, все нечетные числа будут иметь контрольный разряд равный единице, а четные - нулю. Контроль в этом случае сводится к следующим действиям: формированию контрольного разряда на пе- редающей позиции; передаче избыточного кода; проверке сформиро- ванного по тем же правилам контрольного разряда на приемной по- зиции с полученным по каналу контрольным разрядом.
В случае числового контроля по модулю два ошибка не будет обнаружена в том случае, если в результате искажений четное число останется четным, а нечетное - нечетным. Вероятность такого собы- тия близка к 0,5.
Чем больше значение модуля, тем больше число контрольных разрядов добавляется в передаваемое сообщение. В то же время больше вероятность обнаружения ошибок.
Второй метод контроля (цифровой контроль) по модулю преду- сматривает суммирование значений разрядов числа по некоторому

242 модулю в соответствии с выражением
1 0
mod
k
m
i
i
b
m
α
−
=


=






∑
, где
i
b - значение i -го разряда числа;
k
- число разрядов.
Например, для числа x = 1001 контрольный разряд при m = 2 имеет значение
[
]
2 1 0 0 1 mod 2 0
α
= + + +
=
и поэтому избыточный код будет следующим:
2 1001 0
х
=
контрольный разряд.
Очевидно, что при таком кодировании для m = 2 все неисправ- ности, приводящие к искажению одного разряда (трех, пяти и т.д.), обнаруживаются. Если же искажаются два разряда (четыре, шесть и т.д.), то ошибка не будет обнаружена. Однако вероятность появления ошибок одновременно в двух разрядах существенно меньше появле- ния одиночных ошибок.
Схемные методы контроля по модулю 2 называются также кон- тролем по четности. Если контрольным разрядам присваиваются ин- версные значения (
2
α
), то контроль называется проверкой по нечет- ности.
Контроль с проверкой по нечетности (четности) имеет неболь- шую избыточность и не требует больших затрат оборудования для своей реализации. Этот метод широко используется в цифровых уст- ройствах для контроля передачи информации как внутри устройства, так и вне его, а также для контроля информации, считанной из запо- минающего устройства.
6.3.3 Коды, исправляющие ошибки
В исправляющих кодах двоичное число, составленное из кон- трольных разрядов (синдром кода), должно определять порядковый номер искаженного разряда кодового слова. Далее значение искажен- ного разряда инвертируется, чем достигается его коррекция.

243
Примером таких кодов является код Хэмминга. В этом коде кон- трольные суммы составляются так, чтобы в сумму
j
s входили симво- лы кодового слова, имеющие единицу в j - м разряде в двоичной за- писи их порядкового номера. Нетрудно видеть, что при этом симво- лы, порядковый номер которых в двоичной записи выражается еди- ницей j - го разряда, т.е. равен
1 2
,
1, 2, 3,...,
j
j
−
=
войдут только в одну контрольную сумму
j
s . Именно на этих позициях (1-й, 2-й, 4-й, 8-й,
...,
2
i
) в коде Хэмминга и располагаются проверочные символы
2 1
2 4
8
,
,
,
,...
i
β β β β
β
. Соответствующим их выбором все контрольные суммы обращаются в нуль. При отсутствии искажений все контроль- ные суммы останутся равными нулю. Одиночная ошибка, например искажение
l
- го разряда кодового слова, приведет к обращению в единицу контрольных сумм, номера которых соответствуют номерам разрядов двоичной записи числа
l
, содержащих единицы. Поэтому, записывая значения контрольных сумм в порядке убывания их номе- ров, т.е. записывая синдром
4 3
2 1
... ,
,
,
s s s s , получаем в двоичной записи номер l искаженного разряда.
Для наглядности двоичная запись номеров разрядов кодового слова сведена в таблицу 6.1 (таблица приведена для информационных сообщений, представленных в виде пятнадцатиразрядных кодов).
Для пятнадцатиразрядного кода в соответствии с таблицей 6.1 контрольные суммы имеют вид:
1 1
3 5
7 9
11 13 15 2
2 3
6 7
10 11 14 15 3
4 5
6 7
12 13 14 15 4
8 9
10 11 12 13 14 15
;
;
;
s
b
b
b
b
b
b
b
s
b
b
b
b
b
b
b
s
b
b
b
b
b
b
b
s
b
b
b
b
b
b
b
β
β
β
β
=
⊕ ⊕ ⊕ ⊕ ⊕
⊕
⊕
=
⊕ ⊕ ⊕ ⊕
⊕
⊕
⊕
=
⊕ ⊕ ⊕ ⊕
⊕
⊕
⊕
=
⊕ ⊕
⊕
⊕
⊕
⊕
⊕
(6.5) где
i
b - значение информационных символов кода;
1 2
4 8
,
,
,
β β β β
- значения проверочных символов;
⊕
- знак суммирования по модулю два.

244
Таблица 6.1
Значения разрядов двоичной записи порядкового номера разрядов кода
Порядковый номер разряда
4 3
2 1
(младший)
1 (младший)
0 0
0 1
2 0
0 1
0 3
0 0
1 1
4 0
1 0
0 5
0 1
0 1
6 0
1 1
0 7
0 1
1 1
8 1
0 0
0 9
1 0
0 1
10 1
0 1
0 11 1
0 1
1 12 1
1 0
0 13 1
1 0
1 14 1
1 1
0 15 1
1 1
1
Значения проверочных символов
i
β
, отображающие в нуль кон- трольные суммы равны
1 3
5 7
9 11 13 15 2
3 6
7 10 11 14 15 4
5 6
7 12 13 14 15 8
9 10 11 12 13 14 15
;
;
;
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
β
β
β
β
= ⊕ ⊕ ⊕ ⊕
⊕
⊕
= ⊕ ⊕ ⊕
⊕
⊕
⊕
= ⊕ ⊕ ⊕
⊕
⊕
⊕
= ⊕
⊕
⊕
⊕
⊕
⊕
(6.6)
Процедура формирования исправляющего кода Хэмминга вклю- чает, таким образом, следующие операции:
1) расположение информационных символов в порядке возрас- тания разрядов (справа налево) с сохранением незанятыми разрядов с номерами
1 2
j
−
, т.е. 1-го, 2-го, 4-го, 8-го и т.д.;
2) вычисление проверочных символов, занимающих разряды с номерами
1 2
j
−
, по формулам (6.6).
Процедура определения передаваемого информационного кода при использовании исправляющего кода Хэмминга включает:
1) вычисление контрольных сумм по формулам (6.5);
2) определение порядкового номера искаженного символа, если

245 не все контрольные суммы равны нулю, и исправление его на другой двоичный символ;
3) выделение информационного кода исключением разрядов с номерами
1 2
,
1, 2,...
j
j
−
=
Например, если информационный код имеет вид 101001, то его символы располагаются в коде Хэмминга в следующей последова- тельности:
10 9
8 7
6 5
4 3
2 1
1 0
8
β
1 0
0 4
β
1 2
β
1
β
Определим по формулам (6.3) значения проверочных символов:
1 3
5 7
9 2
3 6
7 10 4
5 6
7 8
1 0
1 0
0;
1 0
1 1 1;
0 0
1 1;
0.
b
b
b
b
b
b
b
b
b
b
b
β
β
β
β
= ⊕ ⊕ ⊕
= ⊕ ⊕ ⊕ =
= ⊕ ⊕ ⊕
= ⊕ ⊕ ⊕ =
= ⊕ ⊕
= ⊕ ⊕
=
=
С учетом контрольных разрядов получим следующий код:
1001001110.
Если, например, при приеме пятый разряд этого кода ошибочно будет принят как единица, то контрольные суммы (синдромы) будут иметь значения:
1 1
3 5
7 9
2 2
3 6
7 10 3
4 5
6 4
8 0
1 1
1 0 1;
1 1
0 1
1 0;
1 1
0 1
1;
0.
s
b
b
b
b
s
b
b
b
b
s
b
b
s
β
β
β
β
=
⊕ ⊕ ⊕ ⊕
= ⊕ ⊕ ⊕ ⊕ =
=
⊕ ⊕ ⊕ ⊕
= ⊕ ⊕ ⊕ ⊕ =
=
⊕ ⊕
= ⊕ ⊕ ⊕
=
=
=
Значение синдрома, определяющего номер искаженного разряда в двоичной записи, равно
4 3 2 1 0101
s s s s
=
, что соответствует двоично- му представлению цифры 5 десятичной системе счисления. Для ис- правления ошибки требуется изменить символ в 5-м разряде.

246 6.3.4 Каскадные коды
Возможности кода по обнаружению и исправлению ошибок оп- ределяются величиной избыточности кода. Причем практически без- ошибочная передача информации достигается лишь при весьма зна- чительных длинах кодовых слов. Поиск эффективных схем кодирова- ния и декодирования, сложность реализации которых с ростом длины кода увеличивалась бы как можно медленнее, привел к появлению каскадных кодов.
Обобщенный каскадный код определяется так. Двоичное слово
α
длины
1 2
n
n n
= ⋅
является кодовым словом обобщенного каскадно- го кода порядка m тогда и только тогда, когда все связанные со сло- вом
α
, векторы
,
1,
1
i
i
m
γ
=
+
, представляют собой кодовое слово соответствующих
(
)
i
x
−
кодов второй ступени.
Обобщенному каскадному коду можно дать достаточно нагляд- ную и удобную при многих рассуждениях геометрическую трактовку.
Последовательность
α
двоичных символов, образующих кодо- вое слово обобщенного каскадного кода, разместим в прямоугольную таблицу размером
1 2
n n
⋅
так, что векторы
j
α
являются ее столбцами.
Тогда векторы
1 2
2
,
,...,
i
i
n
α α
α
образуют
i -й горизонтальный блок
i
B этой таблицы, общее число которых равно
1
m
+
, где m - порядок кода.
Каждый горизонтальный блок
i
B , состоящий из
i
α
строк, в свою очередь, разобьем на два блока -
i
К
и
i
L , содержащих соответственно
i
b и
2
i
n
b
−
столбцов.
В блоках
i
К
расположены информационные символы каскадно- го кода, а в блоках
i
L - его проверочные символы (рисунок 6.1). Если
1
m
b
+
= 0, то блок
1
m
B
+
совпадает с
1
m
L
+
и содержит одни лишь прове- рочные символы (рисунок 6.2).
В этом случае столбцы
j
α
являются кодовыми словами некото- рого двоичного линейного кода длины
1
n .
Отметим, что величины
0
i
a
>
и
0
i
b
≥
, определяющие внутрен- нюю структуру обобщенного каскадного кода, могут выбираться произвольно, при этом общее число
k
информационных символов и
r
проверочных символов равны

247
(
)
1 1
2 1
1 1
;
m
m
i i
i
i
i
k