Теорема. Конечный дискретный канал без памяти обладает следующими свойствами.

1. Скорость передачи R является строго выпуклой кверху функцией от вероятностей полученных букв

2. Скорость R является выпуклой кверху функцией от вероятностей букв на входе

3. Область пространства вероятностей букв на входе, в которой достигается пропускная способность канала, является выпуклым множеством.

4. Не существует локального максимума R, который не является абсолютным максимумом С.

5. Любая буква на входе, внутренняя для выпуклого тела, определенного другими буквами на входе, может быть выкинута без снижения пропускной способности канала.

6. Для достижения пропускной способности канала нужно использовать только q (соответствующим образом выбранных) букв на входе, где q равно рангу матрицы

Более того,

7. Пропускная способность является выпуклой вниз функцией переходных вероятностей

Код Хэмминга

Одними из самых простых корректирующих кодов являются коды Хэмминга, представленные Хэммингом в 1950 г. Данные коды обладают кодовым расстоянием

dmin=3 и поэтому способны исправлять только одну или обнаружить две ошибки. Число разрешенных кодовых комбинаций для кодов с d=3 равно N ≤ 2n•(1+n)-1. Для кодов Хэмминга выбрано предельное значение разрешенных кодовых комбинаций N = 2n•(1+n)-1, а число информационных разрядов k определяется как

k = log[ 2n•(1+n)-1 ] = n - log(n + 1).

Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, …., которые и определяют соответствующие коды Хэмминга [3, 1] - код, [7, 4] - код, [15, 11] - код и

т.д. Ниже представлены алгоритмы кодирования и декодирования на примере [7, 4] - кода Хэмминга.

Алгоритм кодирования

Все номера позиций кода нумеруются в двоичной системе счисления, начиная с единицы p-разрядным двоичным числом: p = [ log(n) ], где [ ] - ближайшее большее целое, n - число разрядов кода cncn-1...cj...c1.

Проверочные разряды размещаются в позициях кода, кратных целой степени двойки 20, 21, … и т.д.: cj = bj, j = 2i, i = 0, 1, …, (r-1), где r - число проверочных разрядов.

Значение cj проверочного разряда определяется как сумма по mod2 тех разрядов кода, в номере которых двоичный разряд с i-ым весом равен единице.

Алгоритм декодирования

Вычисляется значение синдрома ошибки: Eош = || hrhr-1...hi...h1 ||.

Значение i-го разряда синдрома определяется как сумма по mod2 тех разрядов принятого кода, включая проверочные, в номере которых вес двоичного разряда совпадает с весом разряда синдрома. Например, для r = 3:

При проверке информации после ее приема возможны три случая:

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

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

· Двойная ошибка - корректирующее число не равно нулю, контроль общей четности кодовой комбинации не обнаруживает ошибки.

Эффективность кода [7, 4]

Код [7, 4] является минимально возможным кодом с достаточно большой избыточностью. Эффективность кода (k/n) растет с увеличением длины кода

Пример

Пусть информационный кодовый вектор v = 1101.

Кодирование

В коде Хэмминга этот вектор будет занимать позиции c3, c5, c6 и c7, начиная с младшего разряда, а позиции c1, c2, c4 отводятся под проверочные разряды кода.

· Шаг 1. Пронумеровать все позиции кода в двоичной системе счисления: c111c110c101[c100]c011[c010][c001] и выделить позиции для размещения проверочных разрядов:

· Шаг2. Определить значения проверочных разрядов кода суммированием по mod2 тех разрядов кода, в номере которых двоичный разряд с (i)-ым весом равен единице:

Таким образом, получен кодовый вектор v = 1100110, который передается по каналу, подверженному влиянию помех.

Пусть вектор ошибки равен e = 0000100, тогда принятая из дискретного канала кодовая комбинация будет иметь вид:

Декодирование

Найти синдром ошибки Eош = || h3h2h1 ||. Для этого

Eош = ||011||. Так как синдром ошибки определяет в двоичной системе номер разряда, в котором обнаружена однократная ошибка, для исправления ошибки

необходимо инвертировать третий разряд - c3. Получим: v = 1100110, откуда, выделяя информационные разряды, получаем исходный кодовый вектор v = 1101.

Матричный подход к построению помехоустойчивых кодов. Проверочная и корректирующая матрицы.

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

Чтобы получить кодовое слово f, нужно информационное слово a умножить на порождающую матрицу G, то есть f = aG. Так, если a = 011 — информационное слово из k = 3 символов и задана порождающая матрица G размерности 3 на 5, то кодовое слово f будет состоять из n = 5 символов, из которых два последних являются проверочными:

Порождающая матрица получается путем последовательного сдвига соответствующего порождающего многочлена по разрядам вправо. Последовательному сдвигу вправо отвечает умножение

Порождающая матрица G имеет размерность поскольку для сдвига берутся степени в пределах а степень порождающего многочлена равна m. Мы знаем, что каждому порождающему многочлену соответствует проверочный многочлен h(x), который удобно записать в порядке убывания степеней:

Причем где, напомним, n — общее число символов, k — число информационных, а m — число проверочных символов в кодовом слове. Если существует порождающая матрица G, то должна существовать и соответствующая ей проверочная матрица H. Действительно, такую матрицу можно получить путем последовательного сдвига проверочного многочлена h(x) влево:

Предположим, у нас есть конкретный порождающий многочлен

Проверочный многочлен h(x) находится простым делением многочлена на заданный многочлен g(x); в результате имеем: =

В соответствии с вышеприведенными определениями, находим конкретный вид порождающей G и проверочной H матриц:

Последнее равенство говорит о том, что матрицы G и H ортогональны относительно друг друга (звездочка означает операцию транспонирования матрицы).

Рассмотренные G и H матрицы называются ленточными, потому что нули и единицы вдоль обеих диагоналей этих матриц образуют своеобразные ленты. Но любая ленточная матрица может быть сведена к систематическому виду:

Существует, по крайней мере, два способа сведения ленточных матриц к систематическому виду. Первый наиболее надежный способ состоит в нахождении ряда остаточных многочленов. Если остаточный многочлен от деления на порождающий многочлен то сумма элементов

дает строки систематической матрицы G. Аналогичным способом находятся строки проверочной матрицы H. Второй способ заключается в том, чтобы найти соответствующие линейные комбинации строк или столбцов исходных матриц ленточного типа. Найдем G и H для предыдущего случая:

Эти две систематические матрицы можно было бы получить путем сложения векторов-столбцов исходных ленточных матриц (напоминаем, счет столбцов для G матрицы начинается с нуля, а для H матрицы — с шести).

Теперь поясним, как составить проверочные соотношения и определить коды ошибок si по известной проверочной матрице. С этой целью выпишем три равенства, отвечающих строкам матрицы H':

При ошибке в символе суммы изменятся на 1, а при ошибке в не будут равны нулю суммы Таким образом, можно составить все коды ошибок для всех символов (табл. 1).

Таблица 1

При одновременном появлении ошибок в двух символах, например в и

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

Код БЧХ

БЧХ-код является циклическим кодом, который можно задать порождающим полиномом. Для его нахождения в случае БЧХ-кода необходимо заранее определить длину кода n(она не может быть произвольной) и требуемое минимальное расстояние Найти порождающий полином можно следующим образом.

Тогда нормированный полином минимальной степени над полем корнями которого являются подряд идущих степеней элемента β для некоторого целого (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем GF(q) с длиной n и минимальный расстоянием

Число проверочных символов r равно степени число информационных символов величина d называется конструктивным расстоянием БЧХ- кода. Если то код называется примитивным, иначе непримитивным.

Так же, как и для циклического кода, кодовый полином c(x) может быть получен из информационного полинома m(x), степени не больше k-1, путем перемножения m(x) и

Построение

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

- выбрать q, то есть поле GF(q), над которым будет построен код;

- выбрать длину n кода из условия где m, s — целые положительные числа;

- задать величину d конструктивного расстояния;

1) Построить циклотомические классы элемента над полем GF(q), где a- примитивный элемент

Циклотомическим классом над полем порождѐ нным некоторым элементом называется множество всех различных элементов являющихся q-ыми степенями α.

2) Поскольку каждому такому циклотомическому классу соответвует неприводимый полином над GF(q), корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать таким образом, чтобы суммарная длина циклотомических классов была минимальна

3) вычислить порождающий полином - полином, соответствующий i -ому циклотомическому классу.

⇐ Предыдущая 11 12 13 14 151617 18 19 20 Следующая ⇒