Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лекция № 13. Корректирующий код Хэмминга
Корректирующий код Хэмминга К систематическим кодам относятся блочные разделимые коды, где операции кодирования осуществляются независимо в пределах каждой комбинации, состоящей из информационных и контрольных символов. Общие принципы построения систематических кодов Если обозначить информационные символы буквами с, а контрольные – буквами е, то любую кодовую комбинацию, содержащую k информационных и r контрольных символов d можно представить последовательностью: c 1, c 2, c 3, …, ck, е 1, е 2, е 3, …, еr, где с и е в двоичном коде принимают значения 0 или 1. Процесс кодирования на передающем конце сводится к образованию контрольных символов, которые выражаются в виде линейной функции информационных символов: , (1) где j = 1, 2,...., r; – коэффициенты, равные 0 или 1; и – знаки суммирования по модулю два. Значения выбираются по определенным правилам, установленным для данного вида кода. Иными словами, символы е представляют собой суммы по модулю два информационных символов в различных сочетаниях. Процедура декодирования принятых комбинаций может осуществляться различными методами. Один из них, так называемый метод контрольных чисел, состоит в следующем. Из информационных символов принятой кодовой комбинации образуется по правилу (1) вторая группа контрольных символов . Затем производится сравнение обеих трупп контрольных символов путем их суммирования по модулю два: (2) Полученное число X называется контрольным числом или синдромом. С его помощью можно обнаружить или исправить часть ошибок. Если ошибки в принятой комбинации отсутствуют, то все суммы , а следовательно, и контрольное число X будут равны нулю. При появлении ошибок некоторые значения х могут оказаться равными 1. В этом случае , что и позволяет обнаружить ошибки. Таким образом, контрольное число X определяется путем r проверок на четность. Для исправления ошибок знание одного факта их возникновения является недостаточном. Необходимо указать номер ошибочно принятых символов. С этой целью каждому сочетанию исправляемых ошибок в комбинации присваивается одно из контрольных чисел, что позволяет по известному контрольному числу определить место положения ошибок и исправить их. Контрольное число X записывается в двоичной системе; поэтому общее количество различных контрольных чисел, отличающихся от нуля, равно . Очевидно, это количество должно быть не меньше числа различных сочетаний ошибочных символов подлежащих исправлению. Например, если код предназначен для исправления одиночных ошибок, то число различных вариантов таких ошибок равно . В этом случае должно выполняться условие . (3) Формула (3) позволяет при заданном количестве информационных символов k определить необходимое число контрольных символов r, с помощью которых исправляются все одиночные ошибки. Коды Хемминга Коды Хемминга относятся к систематическим кодам, позволяющие исправлять все одиночные ошибки. Рассмотрим построение девятизначного кода Хэмминга, каждая комбинация которого содержит пяти информационных и трех контрольных символа. Такой код, условно обозначаемый (9, 5). Он удовлетворяет неравенству (3) и имеет избыточность . Если информационные символы с занимают в комбинации первые пять мест, то последующие четыре контрольных символа образуются по общему правилу (1) как суммы: . (4) Декодирование осуществляется путем четырех проверок на четность (2): (5) Так как x равно 0 или 1, то всего может быть шестнадцать контрольных чисел : 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110 и 1111. Первое из них имеет место в случае правильного приема, а остальные пятнадцать появляются при наличии искажений и должны использоваться для определения местоположения одиночной ошибки в девятизначной комбинации. Рассмотрим, каким образом устанавливается взаимосвязь между контрольными числами и искаженными символами. Если искажен один из контрольных символов: , то, как следует из (5), контрольное число примет соответственно одно из трех значений: 1000, 0100, 0010 или 0001. Остальные четыре контрольных числа используются для выявления ошибок в информационных символах. Порядок присвоения контрольных чисел ошибочным информационным символам может устанавливаться любой, например, как показано в табл. 1. Покажем, что этому распределению контрольных чисел соответствуют коэффициенты , приведенные в табл.2. Таблица 1 Распределение контрольных чисел для определения местоположения ошибки
Таблица 2 Контрольные числа для принятого распределения
Используя коэффициенты из табл. 2, по формуле (5) вычислим контрольные числа: (6) При искажении одного из информационных символов становятся равными единице те суммы х, в которые входит этот символ. В результате получается, что контрольное число согласуется с табл. 1. Нетрудно заметить, что первые четыре контрольные числа в табл. 1 совпадают со столбцами табл. 2. Это свойство дает возможность при выбранном распределении контрольных чисел составить таблицу коэффициентов . Т.о., при одиночной ошибке можно вычислить контрольное число, позволяющее по табл. 1 определить тот символ кодовой комбинации, который претерпел искажения. Исправление искаженного символа двоичной системы состоит в простой замене 0 да 1 или 1 на 0. Рассмотрим пример передачи комбинации, в которой информационными символами является =10011. Используя формулу (4) и табл. 2, вычислим контрольные символы: При этом передаваемая комбинация будет =10011.0110. Предположим, чтопринята комбинация – 1 1 011.0110 (искажен символ с 2). Подставляя соответствующие значения в формулу (6), получим: Вычисленное таким образом контрольное число = 0101 позволяет согласно табл. 1 исправить ошибку в символе с 2 с «1» на «0»: =10011. Следует отметить, что в коде (9, 5) при появлении многократных ошибок контрольное число также может отличаться от нуля. Однако декодирование в этом случае будет проведено неправильно, так как оно рассчитано на исправление лишь одиночных ошибок. Методика кодирования сообщения кодом Хэмминга Процесс кодирования выполняется в 3 этапа: 1. Текстовое сообщение преобразовывается в цифровой код с помощью таблицы кодов русского языка (табл. П.1). 2. Для каждой кодовой комбинации по формуле (4) вычисляются контрольные символы е 1, е 2, е 3, …, еr. 3. По результатам вычисления контрольных чисел формируется избыточный код Хэмминга: c 1, c 2, c 3, …, ck, е 1, е 2, е 3, …, еr. Рассмотрим пример кодирования сообщения «ПРИМЕР». По табл. П.1 преобразуем сообщение в двоичный код (табл. 3). Таблица 3 Кодовые комбинации сообщения
Пользуясь выражением (4), вычислим контрольные символы (табл.4). По результатам расчета сформируем код Хэмминга для приведенного сообщения (табл. 5).
Таблица 4 Контрольные символы
Таблица 5 Код Хэмминга для символов сообщения
Методика декодирования сообщения закодированного кодом Хэмминга В процессе передачи сообщения в канале связи сигнал подвергается искажениям, что приводит к ошибочному приему отдельных элементов кодовой комбинации. При использовании избыточного кода Хэмминга возможно исправление до одной ошибки. Процесс декодирования сообщений закодированных кодом Хэмминга осуществляется в 3 этапа: 1. По принятой кодовой комбинации, используя коэффициенты из табл. 2, по формуле (5) вычисляются контрольные числа (синдром) . 2. Используя таблицу распределения контрольных чисел (см. табл. 1) по результатам расчета синдрома X определяется местоположение ошибки в каждой кодовой комбинации и исправляется ошибка, путем замены ошибочного символа на противоположный: . 3. По результатам декодирования с помощью таблицы двоичных кодов русского алфавита (см. табл. П.1) формируется текст декодированного сообщения. Рассмотрим пример. Предположим, что закодированное сообщение: «ПРИМЕР» подвернулось искажению при передаче в канале связи (табл. 6). Таблица 6 Принятое с ошибками закодированное сообщение
Произведем декодирование. По формуле (5) вычислим контрольные числа синдрома для каждой кодовой комбинации и по табл. 1 определим место ошибочного символа в каждой кодовой комбинации (табл. 7). Таблица 7 Контрольные числа для приятого сообщения
С учетом обнаруженных ошибок и таблицы кодов русского алфавита (см. табл. П.1), составим коды символов (табл. 8). Таблица 8 Кодовые комбинации декодированного сообщения
В результате, получим текст: «ПРИМЕР».
|