Кодирование информации

4.1 Цель работы

Закрепить знания в построении кодов ОНК и помехоустойчивых кодов, в обнаружении и исправлении ошибок.

4.2 Темы лабораторной работы № 4

1. Построить код ОНК по методике Хаффмена.

2. Построить код ОНК по методике Шеннона-Фано.

3. Построить помехоустойчивый линейный систематический код.

4. Построить помехоустойчивый код Хэмминга.

5. Построить циклический код.

6. Исправление ошибок в линейном систематическом коде.

7. Исправление ошибок в коде Хэмминга.

8. Исправление ошибок в циклическом коде.

4.3 Основные определения

Оптимальным кодированием называется процедура преобразования символов первичного алфавита m₁ в кодовые слова во вторичном алфавите m₂, при котором средняя длина сообщений во вторичном алфавите имеет минимально возможную для данного m₂ длину.

Оптимальными называются коды, представляющие кодируемые понятия кодовыми словами минимальной средней длины.

Коды, представляющие первичные алфавиты с неравномерным распределением символов, имеющие среднюю минимальную длину кодового слова во вторичном алфавите, называются оптимальными неравномерными кодами (ОНК).

Эффективность ОНК оценивают при помощи коэффициента статического сжатия

,

который характеризует уменьшение количества двоичных знаков на символ сообщения при применении ОНК по сравнению с применением методов нестатистического кодирования, и коэффициента относительной эффективности

,

который показывает, насколько используется статическая избыточность передаваемого сообщения.

Из свойств оптимальных кодов вытекают принципы их построения:

· Первый принцип оптимального кодирования: выбор каждого кодового слова необходимо производить так, чтобы содержащееся в нем количество информации было максимальным.

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

Принципы оптимального кодирования определяют методики построения оптимальных кодов.

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

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

В общем случае для обнаружения t ошибок минимальное кодовое расстояние

d₀ = t + 1.

Минимальное кодовое расстояние, необходимое для одновременного обнаружения и исправления ошибок,

d₀ = t + s + 1,

где s - число исправляемых ошибок.

Для кодов, только исправляющих ошибки,

d₀ = 2s + 1.

Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода, достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц полученной комбинации.

Для обнаружения и исправления одиночной ошибки соотношение между числом информационных разрядов k и числом корректирующих разрядов r должно удовлетворять следующим условиям:

, ,

при этом подразумевается, что общая длина кодовой комбинации

n = k + t

Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием d₀ = 3 удобно пользоваться выражениями

t₁₍₂₎ = [ log₂ (n + 1) ],

если известна длина полной кодовой комбинации n, и

t₁₍₂₎ = [r log₂ { (k + 1) + [ log₂ (k + 1) ] } ],

если при расчетах удобнее исходить из заданного числа информационных символов k.

Для кодов, обнаруживающих все трехкратные ошибки (d₀=4),

t₁₍₃₎ ³ 1 + log₂ (n + 1),

или

t₁₍₃₎ ³ 1 + log₂ [ (n + 1) + log₂ (k + 1) ]

Для кодов длиной в n символов, исправляющих одну или две ошибки (d₀=5),

t₂ ³ log₂ (C_n² + C_n¹ + 1).

Для практических расчетов можно пользоваться выражением:

.

Для кодов, исправляющих 3 ошибки (d₀=7),

.

4.4 Теоретические сведения

Дата добавления: 2015-08-31