Материал: 838

2) Ошибка в бите 5 — бит 1 заменён на бит 0, принят следующий код: {11110001110}. Просуммируем коды позиций с ненулевыми битами:

Найдена контрольная сумма в кодовых последовательностях, содержащих ошибку не равна 0. В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме.

56

ЛАБОРАТОРНАЯ РАБОТА № 6 Методы логического кодирования (Канальный

уровень). Корректирующие и обнаруживающие коды. Код Хэмминга

Продолжительность — 4 часа. Максимальный рейтинг — 7 баллов.

ЦЕЛЬ РАБОТЫ

Изучить методы логического кодирования, используемые на канальном уровне (OSI) сетевых устройств. Изучить корректирующие и обнаруживающие коды на примере кода Хэмминга.

ЗАДАНИЕ

1.Составить корректирующий код Хэмминга для передачи битовой последовательности длины m (длина информационной последовательности и сама битовая последовательность выбирается из вариантов индивидуального задания). Определить число контрольных битов. Вычислить позиции контрольных битов.

2.Закодировать полученным кодом Хэмминга заданную в индивидуальном задании последовательность.

3.Внести единичную ошибку в кодовую последовательность. Обнаружить и исправить ошибку по алгоритму Хэмминга.

4.Внести двойную ошибку. Обнаружить ее по методу Хэм-

минга.

5.В отчете привести полный расчет кода, обосновать выбор длины контрольной суммы.

ВАРИАНТЫ ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Основные функции методов логического кодирования.

2.Корректирующие и обнаруживающие коды. Кодовое расстояние.

3.Обнаруживающая способность кода. Корректирующая способность.

4.Линейные коды. Систематические линейные коды. Совершенные и квазисовершенные коды.

58

5.Циклические коды. CRC. Порждающий многочлен. Алгоритм кодирования\декодирования.

6.Код Хэмминга. Размер кодовой последовательности. Позиции кодовых знаков.

59

7 КОДИРОВАНИЕ ИНФОРМАЦИИ. КОМПРЕССИЯ. МЕТОД ХАФФМАНА

Метод Хаффмана (Huffman code) или минимально-избы-

точный префиксный код (minimum-redundancy prefix code) отно-

сится к статистическим методам кодирования.

Обычно для хранения данных и передачи сообщений используются коды фиксированной длины, например, код ASCII. Множество символов представляется некоторым количеством кодовых слов равной длины, которая для кода ASCII равна 8 битам. При этом для всех сообщений с одинаковым количеством символов требуется одинаковое количество битов при хранении и одинаковая ширина полосы пропускания при передаче.

Метод Хаффмана основан на кодировании более короткими кодовыми словами часто встречающиеся символы, а символы встречающиеся редко — более длинными. Подбирая кодовые последовательности таким образом, можно получить код с длиной, очень близкой к его энтропии (то есть информационной насыщенности). Кодовые слова при этом должны быть выбраны так, чтобы никакое из них не было префиксом другого кодового слова. Благодаря этому условию гарантируется возможность однозначного декодирования определенного закодированного текста.

В своей статье, опубликованной в 1952 г., Дэвид Хаффман описал алгоритм поиска множества кодов, которые минимизируют ожидаемую длину сообщений при условии, что известны вероятности появления каждого символа. В этом методе символам, имеющим меньшую вероятность появления, ставятся в соответствие более длинные кодовые слова.

Пусть A a1,a2,...,an — алфавит из n различных симво-

лов, P p1, p2,..., pn — соответствующий ему набор положи-

тельных весов (вероятностей).

Тогда набор бинарных кодов C c1,c2,...,cn , такой что:

(1) ci не является префиксом для cj, при i j;

n

(2)pi ci — минимальна

i 1