Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 17

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 11 12 13 14 15 16 < 17 > 18 19 20 21 22 23 .. 50 >> Следующая


46 рочных символов. Оставшиеся Im—J—т символов являются информационными. Проверки строятся по аналогии с рассмотренным случаем. Значения т проверок, как и выше, образуют номер положения ошибки.

Вернемся, однако, к вопросу, поставленному в начале этого параграфа. Добавим к кодовым словам кода Хеммин-га длины 7 еще один проверочный символ Ct0, а к проверочным соотношениям (5) еще одно (общую проверку на четность):

So=oco+a1+a24-a3+a4+a6+a1i+a7=0. (6)

Новый код по-прежнему будет содержать 16 кодовых слов, потому что, как и раньше, символы ait а2, а3, сс4 могут быть взяты какими угодно; по ним из соотношений (1) определяются символы сс5, ae, а7, а из равенства (6) и символ <х0. В случае одиночной ошибки добавленное соотношение (6) нарушается, а значения S1-, s2, S3 образуют номер положения ошибки. Если же произошла двойная ошибка, то соотношение (6) будет выполнено, а хотя бы одно из равенств (5) нарушится (почему?). Это и позволяет обнаружить любую двойную ошибку. Итак, для исправления одиночных и обнаружения двойных ошибок к четырем информационным символам достаточно добавить четыре проверочных символа. Можно показать, что обойтись меньшим числом проверочных символов невозможно.

Построенное множество кодовых слов а0аіОі-2аза.4а5а6а.7, удовлетворяющих соотношениям (5) и (6),— пример расширенного кода Хемминга (длины 8 с четырьмя информационными символами).

Задачи и дополнения

1. Определить положение одиночной ошибки R искаженном слове 1100011 кода Хемминга длины 7.

2. Пусть 11010011 и 11001111—искаженные слова расширенного кода Хемминга длины 8. Какое из этих слов содержит одиночную, а какое — двойную ошибку? В случае одиночной ошибки определить ее положение.

3. К проверкам кода Хемминга длины 7 добавим (не меняя длины кода) общую проверку на четность:

^1+?+?+?+°?+?+°'-;==0- (7)

Сколько слов удовлетворяет соотношениям (5) и (7)?

4. Доказать, что код из задачи 3 исправляет одиночные и обнаруживает двойные ошибки.

5. Построить систему проверок для кода Хемминга длины 15. Сколько кодовых слов содержит этот код? Сколько информационных и сколько проверочных символов имеется в кодовом слове? 6. Пели задан код Хемминга длины п= 2m—1, то существуют два простых способа получить из него коды с исправлением одиночных и обнаружением двойных ошибок.

Первый из них (он аналогичен способу, разобранному в конце этого параграфа) таков: к кодовым словам добавляем проверочный символ Ct0, а к проверочным соотношениям кода Хемминга — общую проверку п

на четность: 2 OS1- = 0.

і= о

Во втором способе (см. задачу 3) длина кодовых слов не меняется;

п

но добавляется общая проверка на четность: 2 аг- = 0.

i=l

Сколько информационных и проверочных символов содержится в каждом из описанных здесь кодов?

10. НЕОБЫЧНОЕ ОБЫЧНОЕ РАССТОЯНИЕ

Известно, что расстояние между точками в пространстве определяется как длина отрезка прямой, соединяющей эти точки. Оно служит мерой близости точек — чем меньше расстояние, тем ближе друг к другу расположены точки. Если обозначать расстояние между точками а и b через р (а, Ь), то для любых точек a, b и с имеем:

1) р(а,6)>0;

2) р (о,?>)=0 означает, что а=Ь;

3) p(a,b)=p(b, а)

4) р (a,b)+p(b,c)^p(a,c).

(Последнее условие, называемое неравенством треугольника, означает, что длина любой стороны треугольника не превосходит суммы длин двух других сторон.)

Иногда удобно бывает определить меру близости или расстояние для элементов того или иного множества, даже если эти элементы и не являются точками в обычном смысле. При этом считается, что расстояние между элементами множества определено, если любым двум элементам а и b сопоставлено действительное число р (а, Ь) и для любых элементов а, b и с данного множества выполняются условия 1) — 4).

Вернемся теперь к нашей основной техме. Мы уже знаем, что код тем лучше приспособлен к исправлению ошибок, чем больше отличаются друг от друга кодовые слова. Эту мысль можно будет выразить точно, если ввести расстояние на множестве «-буквенных слов.

Расстоянием р (х, у) между двумя словами хну назовеїч число несовпадающих позиций этих слов. Например, расстояние между словами ^=OllOl и у—00111 равно 2.

48 Определенное так расстояние называют расстоянием Хемминга. Не составляет большого труда проверить, что все свойства 1) — 4) расстояния в данном случае выполнены. Вопрос лишь в том, в какой мере это понятие поможет оценить способности кода исправлять и обнаруживать ошибки. Чтобы ответить на этот вопрос, введем для произвольного кода понятие кодового расстояния.

Кодовое расстояние d(V) определим как минимальное расстояние между различными кодовыми словами из V:

d(V) = min р (х, у).

хфу

Введенная только что величина является основным показателем корректирующих возможностей кода, поскольку верно следующее утверждение:

Код способен исправлять любые комбинации из t (и меньшего числа) ошибок тогда и только тогда, когда его кодовое расстояние больше 2t.

В самом деле, если d (V)>2t, то для любых кодовых слов X, у имеем р(х, ?/)^2/+1. Пусть при передаче некоторого слова X произошло r^t ошибок, и в результате было принято слово Z. Тогда р(х, z)=r^.t, и в то же время расстояние р (г, у) до любого другого кодового слова у больше t. Последнее вытекает из неравенства треугольника:
Предыдущая << 1 .. 11 12 13 14 15 16 < 17 > 18 19 20 21 22 23 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed