![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лекция № 13. Корректирующий код Хэмминга
Корректирующий код Хэмминга К систематическим кодам относятся блочные разделимые коды, где операции кодирования осуществляются независимо в пределах каждой комбинации, состоящей из информационных и контрольных символов. Общие принципы построения систематических кодов Если обозначить информационные символы буквами с, а контрольные – буквами е, то любую кодовую комбинацию, содержащую k информационных и r контрольных символов d можно представить последовательностью: c 1, c 2, c 3, …, ck, е 1, е 2, е 3, …, еr, где с и е в двоичном коде принимают значения 0 или 1. Процесс кодирования на передающем конце сводится к образованию контрольных символов, которые выражаются в виде линейной функции информационных символов:
где j = 1, 2,...., r; Значения Процедура декодирования принятых комбинаций может осуществляться различными методами. Один из них, так называемый метод контрольных чисел, состоит в следующем. Из информационных символов принятой кодовой комбинации
Полученное число X называется контрольным числом или синдромом. С его помощью можно обнаружить или исправить часть ошибок. Если ошибки в принятой комбинации отсутствуют, то все суммы Для исправления ошибок знание одного факта их возникновения является недостаточном. Необходимо указать номер ошибочно принятых символов. С этой целью каждому сочетанию исправляемых ошибок в комбинации присваивается одно из контрольных чисел, что позволяет по известному контрольному числу определить место положения ошибок и исправить их. Контрольное число X записывается в двоичной системе; поэтому общее количество различных контрольных чисел, отличающихся от нуля, равно
Формула (3) позволяет при заданном количестве информационных символов k определить необходимое число контрольных символов r, с помощью которых исправляются все одиночные ошибки. Коды Хемминга Коды Хемминга относятся к систематическим кодам, позволяющие исправлять все одиночные ошибки. Рассмотрим построение девятизначного кода Хэмминга, каждая комбинация которого содержит пяти информационных и трех контрольных символа. Такой код, условно обозначаемый (9, 5). Он удовлетворяет неравенству (3) Если информационные символы с занимают в комбинации первые пять мест, то последующие четыре контрольных символа образуются по общему правилу (1) как суммы:
Декодирование осуществляется путем четырех проверок на четность (2):
Так как x равно 0 или 1, то всего может быть шестнадцать контрольных чисел Рассмотрим, каким образом устанавливается взаимосвязь между контрольными числами и искаженными символами. Если искажен один из контрольных символов: Таблица 1 Распределение контрольных чисел для определения местоположения ошибки
Таблица 2 Контрольные числа для принятого распределения
Используя коэффициенты
При искажении одного из информационных символов становятся равными единице те суммы х, в которые входит этот символ. В результате получается, что контрольное число Т.о., при одиночной ошибке можно вычислить контрольное число, позволяющее по табл. 1 определить тот символ кодовой комбинации, который претерпел искажения. Исправление искаженного символа двоичной системы состоит в простой замене 0 да 1 или 1 на 0. Рассмотрим пример передачи комбинации, в которой информационными символами является При этом передаваемая комбинация будет Вычисленное таким образом контрольное число Следует отметить, что в коде (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. Используя таблицу распределения контрольных чисел (см. табл. 1) по результатам расчета синдрома X определяется местоположение ошибки в каждой кодовой комбинации и исправляется ошибка, путем замены ошибочного символа на противоположный: 3. По результатам декодирования с помощью таблицы двоичных кодов русского алфавита (см. табл. П.1) формируется текст декодированного сообщения. Рассмотрим пример. Предположим, что закодированное сообщение: «ПРИМЕР» подвернулось искажению при передаче в канале связи (табл. 6). Таблица 6 Принятое с ошибками закодированное сообщение
Произведем декодирование. По формуле (5) вычислим контрольные числа синдрома для каждой кодовой комбинации и по табл. 1 определим место ошибочного символа в каждой кодовой комбинации (табл. 7). Таблица 7 Контрольные числа для приятого сообщения
С учетом обнаруженных ошибок и таблицы кодов русского алфавита (см. табл. П.1), составим коды символов (табл. 8). Таблица 8 Кодовые комбинации декодированного сообщения
В результате, получим текст: «ПРИМЕР».
|