Дискретная математика. Ерош И.Л - 136 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

136
Пример 2. Пусть требуется передать 16 различных сообщений (на
пример, букв или символов). Закодируем эти сообщения 4разрядны
ми двоичными кодами и поставим им в соответствие последователь
ность x
3
, x
5
, x
6
, x
7
. Зарезервируем дополнительные разряды x
1
, x
2
, x
4
для контроля. Будем вычислять значения контрольных разрядов по
следующему правилу:
1
2
3
4
5
6
7
1010101
0110011 0.
0001111
x
x
x
x
x
x
x
12
34
34
34
12
34
34
56
34
34
34
34
7 8
34
34
34
34
7 8
Таким образом, получаем x
1
Å x
3
Å x
5
Å x
7
= 0, x
2
Å x
3
Å x
6
Å x
7
= 0,
x
2
Å x
3
Å x
6
Å x
7
= 0, откуда легко находятся значения контрольных
разрядов x
1
, x
2
, x
4
.
Пусть передаваемое сообщение имело вид 1011. Тогда значения кон
трольных разрядов определятся следующим образом: x
1
= 0, x
2
= 1,
x
4
= 0. Вместо сообщения 1011 будет передано сообщение: 0 1 1 0 0 1 1.
Пусть теперь в результате одиночной ошибки сообщение при передаче
исказится и станет таким 0 1 1 0 0 0 1, т. е. исказился 6й разряд со
общения. При проверке сообщения получаем двоичный код искажен
ного разряда: 1 1 0 (6й разряд). Добавив по модулю 2 единицу в 6й
разряд, мы исправим сообщение. Приведенный пример является совер
шенным кодом Хэмминга, который исправляет одиночные ошибки.
6.2.3. Арифметические коды
Арифметические коды (или ANкоды) предназначены для коррек
ции ошибок при выполнении арифметических операций. Код опреде
ляется значением A, а слова из диапазона 0, 1, 2, …, N–1 кодируются
умножением на A.
Вектор одиночной ошибки представляет собой величину +1 или –1,
которая арифметически складывается с кодовым словом (с учетом пе
реносов, в отличие от ошибок в каналах связи). Для того чтобы код,
порождаемый числом A длины n, исправлял одиночные арифметичес
кие ошибки, необходимо и достаточно, чтобы не выполнялось сравне
ние 2
s
º 2
k
mod A, где s ¹ k; s, k Î{0, 1, 2, …, n–1}.

Страницы