Составители:
3
1. Корректирующее кодирование
1.1. Основные понятия и определения
Корректирующий код предназначен для обнаружения и исправления кодовых ошибок.
Принцип такого кодирования основан на создании избыточности в коде. Под этим
понимается введение дополнительных проверочных бит в последовательность
информационных данных. Поэтому кодирование – это процесс вычисления проверочных
бит, а декодирование – процесс обнаружения ошибок и их исправление. Чем больше
избыточность корректирующего кода, тем выше его обнаруживающая и исправляющая
способности. При этом, естественно, возрастает скорость цифрового потока и
уменьшается длительность записи на носителе. В цифровой звукозаписи для обнаружения
и исправления кодовых ошибок используется только блоковое кодирование
Блоковое кодирование – это кодирование без памяти, потому что кодирование и
декодирование таких кодов осуществляется на основе данных только одного блока.
Блоковый код может быть двоичным и недвоичным. В общем случае основой блокового
кода является символ. Длина символа равна m бит и рассматривается как единое целое. В
частном случае, когда m = 1, код становится двоичным. С символами оперируют также
как с битами.
При блоковом кодировании звука последовательность цифровых выборок левого и
правого звуковых каналов разбивается на символы длиной 4, 8 или 16 бит. Эти символы
образуют информационное слово из k символов. При кодировании в блок добавляется
r
проверочных символов длиной
m
, которые формируют проверочное слово. В результате
кодирования формируется кодовое слово длиной
n k r
символов, и такой код
обозначается, как
( , )nk
. Введение проверочных символов создает избыточность кода,
определяемая равенством
nk
R
n
,
где
r n k
.
Если проверочные символы располагаются в конце блока, тогда код называется
симметричным. Номера всех символов в блоке i отсчитываются справа налево от нуля,
этот номер определяет позицию символов в блоке и называется локатором. При
выполнении математических операций символы и слова могут быть представлены
векторной форме. В процессе корректирующего кодирования и декодирования вектора
можно умножать, делить и суммировать по правилам многочленов из векторной алгебры.
Важнейшим понятием блокового кодирования является поле кода, под которым
понимается все конечное множество кодовых комбинаций бит в символе, для которых
определены правила выполнения всех математических операций (сложение,
умножение…..). Такие конечные поля называются полями Галуа и обозначаются как
GF(2
m
). Число элементов поля называется его порядком и определяется как
2
m
.
Двоичное поле (в этом поле m = 1, = 2). Элемент поля (символ) может принимать
только два значения 0 и 1. Математические правила: 0 + 0 = 0, 1+1 = 0, 0+1 = 1+0 = 1, 0 1
= 1 0 = 0, 0 0 = 0 и 1 1 = 1. Информационные и кодовые слова блока в двоичном поле
могут быть представлены в двоичной форме или в виде степенного полинома. В
процессе корректирующего кодирования вектора можно умножать, делить и суммировать
по правилам многочленов из векторной алгебры. Кодовое слово длиной
n
обычно
