Навигация
5. ОБНАРУЖИВАЮЩИЕ КОДЫ
Обнаруживающие коды - это коды, позволяющие обнаружить ошибку, но не исправить ее. Простейший способ обнаружения ошибки это добавление к последовательности битов данных еще одного бита-бита проверки на четность (нечетность) значение, которого равно сумме по модулю два исходной последовательности битов. Чаще организуется проверка на нечетность.
В символьном коде ASCII к семи битам кода добавляется восьмой бит проверки на четность - k1.
S1 S2 S3 S4 S5 S6 S7 K1
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Однобитовая проверка позволяет обнаружить любую единичную ошибку, две ошибки обнаружить нельзя, в общем случае обнаруживается любое нечетное количество ошибок.
Внесение избыточности за счет увеличения длины кодовой комбинации приводит к снижению скорости передачи информации.
Если скорость идеально использует канал, то
.
(11)
Если кодовая комбинация длиной n содержит k информационных и m контрольных разрядов (n = k + m), то
.
Для кода ASCII n = 8 и k = 7
,
т. е. введения одного избыточного разряда приводит к уменьшению пропускной способности канала связи на 12,5%.
Чаще всего шумы (молнии, разрыв и т.д.) порождают длинные пакеты ошибок и вероятность четного и нечетного числа ошибок одинакова, а значит и однобитовая проверка не эффективна.
Проверка на четность по вертикали и горизонтали. При этом последовательность битов данных перестраивается в двухмерный массив, и вычисляются биты на четность, как для каждой строки, так и для каждого столбца.
При этом можно обнаружить несколько ошибок, если они не располагаются в одинаковых строках и столбцах.
Чаще всего используется при передаче данных кода ASCII; каждый символ можно считать строкой массива. Такая проверка может не только установить факт ошибки, но и обнаружить ее место, а значит, есть принципиальная возможность ее исправления, хотя это практически не используется.
1 0 1 1 0 1 1 1
0 1 0 0 0 1 0 0
1 0 1 0 0 1 0 1
1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 0
1 0 0 0 1 0 0
После обнаружения ошибок иногда можно повторить передачу сообщений, иногда после обнаружения ошибки предпринимается вторая и даже третья попытка передачи сообщения.
Проверка на четность широко используется на ЭВМ, как на аппаратном, так и на программном уровне.
Например, при считывании с магнитной ленты в случае, когда условие на четность не выполняется, то производится повторное считывание, т. е. если произошла малая потеря намагниченности, то после второй попытки может быть считывание произойдет правильно.
Пример 1. Символы алфавита источника кодируются семиразрядным двоичным кодом с весом кодовых векторов (количеством единиц в кодовой комбинации) w = 3. Определить необходимую мощность кода и его избыточность.
Решение: Мощность семиразрядного кода равна N = 27 = 128.
Так как для кодирования используются только кодовые вектора с весом три , то количество таких векторов в семиразрядном коде равно
Избыточность кода равна R = 1 – log2K/ log2N = 0,265.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПб ГИТМО (ТУ), 2001;
2. Мастрюков Д. Алгоритмы сжатия информации. Ч. 1. Сжатие по Хаффмену //Монитор, 1993. – № 7 – 8 – С. 14 – 20;
3. Мастрюков Д. Алгоритмы сжатия информации. Ч. 2. Арифметическое кодирование //Монитор, 1994 – № 1 – С. 20 – 23;
4. Ф.Дж.Мак-Вильямс, Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки, Москва, “Связь”, 1979.
5. .Лидл, Г.Нидеррайтер, Конечные поля, Т. 1,2, Москва, “Мир”, 1988.
6. Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки, Теория кодирования, Москва, “Мир”, 1978.
7. У.Петерсон, Э.Уэлдон, Коды, исправляющие ошибки, Москва, “Мир”, 1976.
8. Э.Берлекэмп, Алгебраическая теория кодирования, Москва, “Мир”, 1971.
9. Дискретная математика и математические вопросы кибернетики. Т.1. /Ю.Л. Васильев, Ф. Я. Ветухновский, В. В. Глаголев, Ю. И. Журавлев, В. И. Левенштейн, С. В. Яблонский. Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Главная редакция физико – математической литературы изд–ва «Наука», 1974
10. Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2004
Похожие работы
... практическое применение классификации. Поэтому на практике глубина классификации обычно не превышает 10. Именно такая глубина применяется во многих классификаторах. 3. Характеристика отечественных систем классификации и кодирования товаров 3.1 Системы классификации товаров В товароведении используют следующие системы классификации товаров: - Торговая система классификации является ...
... на полиграфическую печать окупаются при нанесении штрихового кода более чем на 1000 упаковок товара; в виде самоклеющихся пленок, ярлыков и т. д. [4, c. 149]. Внедрение технологии штрихового кодирования базируется на государственных стандартах, гармонизированных с международными стандартами, регламентирующих: правила построения, термины и определения и требования к символикам штриховых кодов; ...
... кодирования можно разработать устройство, которое поможет понять принцип работы метода Хэмминга. Кодер – декодер будем разрабатывать на основе ИМС К555ВЖ1. 2.1 Разработка устройства кодирования информации методом Хемминга Кодер, преобразует 32х битное слово в 38ми разрядный код Хэмминга, после чего слово хранится в памяти или передаётся по шинам и т.д. В процессе передачи или хранения в ...
... . Универсальным устройством для автоматизированного выполнения информационных процессов в настоящее время является компьютер. Немалую роль в этом играют вычислительные системы и сети. 2. Кодирование информации Информационный процесс кодирования информации встречается в нашей жизни на каждом шагу. Любое общение между людьми происходит именно благодаря тому, что они научились выражать образы ...
0 комментариев