2) Вероятность ошибки оптимального декодирования для кодов с фиксированной длиной блоков (экспоненты вероятностей ошибок)

Пусть имеется некоторый, канал связи, который описывается условными переходными вероятностями Р(у | х), х є Хⁿ, y є Yⁿ, где X и Y - его входной и выходной алфавиты, а Xⁿ и Yⁿ означают всевозможные последовательности длины n из алфавитов X и Y соответственно. Обозначим через р_од(V,S) вероятность ошибочного декодирования в таком канале при использовании некоторого кода V, состоящего из М комбинаций, и алгоритма декодирования по максимуму правдоподобия, если передаётся сообщение S, 1 ≤ S ≤ М. Достаточно общая верхняя граница для р_од ( V,S) при наилучшем выборе кода V была получена Р. Галлагером.

Существует блоковый код V длины n, состоящий из М комбинаций, для которого при передаче произвольного сообщения S, 1 ≤ S ≤ М,

где P(у | х) — переходная условная вероятность для блоков длины n в заданном канале связи; Q(x) — произвольное вероятностное распределение на входных блоках длины n.

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

Для 2СК без памяти с вероятностью ошибки символа р получается решение в замкнутом виде

при

Неравенство (7.21) позволяет сделать важный вывод, что при R < С (Е(R) > 0) вероятность ошибки при выборе наилучшего кода не только убывает к нулю при n→∞, но убывает и как экспонента от n. Именно поэтому границы подобного типа называются экспонентами вероятностей ошибок.

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

3) Коды с гарантированным обнаружением и исправлением ошибок

Пусть задан некоторый блоковый код длины n, состоящий из М комбина­ций (блоков, слов, векторов) X₁, Х₂ , •••, Х_M. Будем всюду считать, что входной X и выходной Y алфавиты канала совпадают. В общем случае канал может иметь память и задаваться вероятно­стями p(х|у) переходов входных блоков х в выходные у.

Определение 1. Расстоянием Хэмминга ρ(х, х') между двумя комбинациями х є Хⁿ и х' є Хⁿ будем называть число позиций этих комбинаций, в которых отдельные кодовые символы х и х' не совпадают. Очевидно, что 1≤ ρ (х, х') ≤ n для любых х’ ≠ х, и что ρ (х, х) = 0 для любых х є Хⁿ.

Определение 2. Образцом ошибки е будем называть двоичный блок длины n, который имеет единицы в тех позициях, в которых символы переданного х и принятого у блоков отличаются друг от друга, и нули — в остальных позициях.

Определение 3. Весом Хэмминга |х| блока (вектора) х называют число ненулевых символов этих блоков.

Определение 4. Кратностью образца ошибки е (или короче — кратностью ошибки) будем называть его вес Хэмминга |е|. (По существу это число ошибок, которое произошло при передаче блока х).

4) Линейные двоичные коды для обнаружения и исправления ошибок. Важные подклассы линейных двоичных кодов.

Определение 1. Линейным блочным двоичным кодом длины п называется лю­бое множество двоичных последовательностей длины п, которое содержит чис­то нулевую последовательность, и для каждой пары последовательностей, при­надлежащих этому множеству, их поразрядная сумма по mod 2 также является элементом этого множества.

Пример. Множество последовательностей длины 5: 00000, 11101, 01010, 10111, образует линейный код, что проверяется непосредственно. Поразрядная сумма по mod2 2-й и 3-ей комбинации даёт 4-ю комбинацию, сумма 3 и 4 даёт 2-ю, а сумма 2 и 4 даёт 3-ю комбинацию.

Линейный код удовлетворяет определению линейного подпространства V для пространства V* всех двоичных последовательностей длины п.

Из алгебры известно, что всякое k-мерное линейное подпространство п- мерного пространства, состоящего из конечного числа (2ⁿ) элементов, содер­жит базис, т.е. совокупность k линейно независимых элементов, из которых пу­тём поразрядного суммирования по mod 2 можно образовать любые элементы данного подпространства, т.е. в данном случае комбинации линейного кода.

Совокупность элементов базиса, записанная в виде линейно независимых строк, образует k×n двоичную матрицу G, которая называется порождающей матрицей кода:

Множество всех кодовых слов, порождённых G, может быть представлено как x = bG,

где х — вектор-строка кодовой комбинации размерности n;

b — вектор-строка информационных символов длины k.

Здесь выполняется умножение вектора на матрицу, а все действия осуществлены по mod 2. В качестве вектора b можно использовать k последовательных элементов сообщения, вы­даваемых двоичным источником. Переход от избыточных кодов общего вида к линейным кодам практически решает проблему сложности кодирования. Дейст­вительно, вместо запоминания М= 2^k комбинаций длины п, т.е. п2^k бит в об­щем случае, нам достаточно запомнить лишь порождающую матрицу, состоя­щую из пк = n log₂М бит. Сама же процедура кодирования потребует выполне­ния не более чем 2kn элементарных операций.

Для любого линейного кода, заданного некоторой порождающей матрицей G, очевидно также следующее свойство: любые перестановки столбцов и эле­ментарные преобразования строк, заключающиеся в их перестановках или в суммировании друг с другом, не изменяют список весов данного кода. При помощи таких преобразований любая (k х n) двоичная матрица G с линейно-независимыми строками может быть приведена к каноническому виду

где { p_ij — некоторые двоичные элементы; I_k — единичная k х k матрица (с еди­ницами на главной диагонали и нулями в других местах); Р — матрица k х (n-k), состоящая из двоичных элементов; (A | B) означает последователь­ную запись матриц А и В}.

Тогда x=(b | c), (7.49)

где с = bР.

По правилу матричного умножения получаем для с = (c₁, ..., c_n-k)

c_j = сумм(i от 1 до k)(b_i p_ij (mod 2)), i=1, 2, ..., n-k.

Определение 2. Линейные коды, слова которых представимы в виде x=b/c, называются систематическими. Всякий линейный код эквивалентен некоторому систематическому в смысле сохранения списка весов, а, следова­тельно, и расстояний Хэмминга. Первые k символов кодовых слов, совпадаю­щих с символами источника, называются информационными, а последние n-k символов — проверочными.

Скорость кода R, определённая ранее как log₂(М/n), для-линейного кода будет равна k/n, т.е. для систематического — отношению числа информационных символов k к длине кодового блока n. Систематиче­ские коды с длиной блока n и с числом информационных символов k будем кратко называть (n, k)-кодами. Иногда такой код обозначают тремя параметра­ми (n, k, d), где d — минимальное кодовое расстояние.

В линейной алгебре существует понятие ортогонального пространства или нуль-пространства для заданного линейного пространства V. Это по определе­нию такое множество V* векторов х* длины n, для которых (х*, х) = 0 при лю­бом хє V, где (, ) означает скалярное произведение соответствующих векторов (В нашем случае все операции производятся по mod2).

Доказывается, что это множество всегда является линейным пространством, причём если код V имеет размерность k, то код V* будет иметь размерность n-k, т.е. содержать 2^n-k комбинаций. Код V*, совпадающий с ортогональным пространством, называет­ся дуальным к коду V. Он, очевидно, также может быть задан своей порождаю­щей матрицей G*=H размерностью (n-k) х n. Тогда комбинации исходного кода V могут быть определены как решения векторно-матричного уравнения

V = {х : хH^T = 0}, (7.51)

где Т означает символ транспонирования матрицы Н, т.е. взаимную замену строк и столбцов. Матрица Н, которая является порождающей для кода V*, называется проверочной матрицей для исходного кода V. Матрица Н так же, как и G, может быть представлена в канонической форме, причём можно показать, что Н=( -P^T | I_n-k).

Определение 3. Синдромом по коду V для любого принятого на выходе канала связи двоичного слова y длины n будем называть двоичный вектор-строку длины n-k: s = yH^T,

где Н — проверочная матрица кода V.

Оптимальное декодирование в 2СК без памяти можно производить, отыскивая слово минимального веса, синдром которого совпадает с синдромом, полученным по принятому слову. Такой алгоритм декодирования называется синдромным.

Схемы кодирования и вычисления синдрома для произвольного линейного кода приведены на рисунках:

Элемент порождающей матрицы p_ij оп­ределяет характер связи i-й ячейки регистра с j-м сумматором: если p_ij = 1 — связь есть, если p_ij = 0 — связь отсутствует. Кодирование происходит следую­щим образом: вектор b записывается в регистр, после чего с выходов суммато­ров считывается вектор с. Для кодирования систематического кода необходимо лишь п-к сумматоров, связи которых с регистром задаются матрицей Р. При этом вектор х образуется из вектора b и выходов п-к сумматоров (вектора с).

Элемент проверочной матрицы h_ij определяет характер связи i-й

ячейки регистра с j-м сумматором: если h_ij =1 — связь есть, если h_ij = 0 — связь

отсутствует. Для вычисления синдрома вектор у записывается в регистр, после чего с выходов сумматоров считывается s.

Важные подклассы линейных двоичных кодов.

Коды с общей проверкой на чётность. Это класс кодов с параметрами (n, k) = (k + 1, k), k = 1, 2, ..., когда имеется лишь один проверочный символ, ко­торый образуется как сумма по mod 2 всех информационных символов. Оче­видно, что минимальное расстояние d для данных кодов всегда равно 2 и по­этому они могут гарантированно обнаруживать лишь одну ошибку. Комбина­ции данного кода имеют лишь чётные веса.

Коды Хэмминга. Данный класс кодов имеет параметры (n, k) = (2^s -1, 2^s -1-s), s — целое. Он определяется проверочной матрицей Н, ко­торая должна содержать все 2^s — 1 ненулевых двоичных векторов. Легко видеть, что данный класс кодов имеет при любых s минимальное кодовое расстояние, равное 3. Это пример совершенного кода, исправляющего все однократные ошибки и ничего более. Коды Хэмминга могут гарантированно обнаруживать ошибки кратности 1 и 2.

Модифицированный код Хемминга (КХМ) способен обнаруживать двойные ошибки, а так же ошибки нечётной кратности, плюс к этому – исправлять одиночные ошибки.

М-последовательности. Это класс кодов с параметрами (п, к) = (2^S -1, s), s — целое, которые определяются как дуальные к кодам Хэмминга той же самой длины. Данный класс кодов может быть определён также иначе, как совокуп­ность выходных последовательностей при различных начальных заполнениях линейного регистра длины s со связями, выбранными так, чтобы период вы­ходной последовательности оказался равным 2^S -1. Поэтому они получили на­звание последовательностей максимальной длины или М-последовательностей. Все комбинации данного кода, кроме нулевой, имеют одинаковый вес 2^{S - 1} и, следовательно, для такого кода d = 2^{S - 1}. Коды Хэмминга и М- последовательности являются крайними случаями кодов с малой и большой величиной минимального кодового расстояния. Они не всегда удобны для практического использования, поскольку исправление только однократных ошибок обычно оказывается недостаточным для обеспечения высокой верно­сти передачи, а высокая исправляющая способность М-последовательностей покупается за счёт их весьма низкой кодовой скорости R. Поэтому необходимо иметь класс кодов с промежуточными значениями R. Это может быть достиг­нуто при переходе к определённым подклассам циклических кодов.

Полиномиальные коды. Циклические коды. Коды Боуза-Чоудхури- Хоквингема (БЧХ). Кодовые слова двоичного линейного кода могут быть пред­ставлены в виде полиномов

x(D) = x₀+x_lD + x₂D²+...+x_{n – l} D^{n - l} степени п-1 от не­которой формальной переменной D, причём двоичные коэффициенты х_i за­дают символы кодового слова.

Полиномиальный код определяется как множест­во полиномов (кодовых слов) степени п -1, получаемых умножением инфор­мационного полинома b(D) степени k-1 на порождающий полином кода g(D) степени п-к: x(D) = b(D)g(D).

Уравнение задаёт процедуру кодирования полиномиального кода: со­общение дискретного источника кодируется примитивным кодом длины к, символы примитивного кода становятся коэффициентами информационного полинома b(D) = b₀+b₁D+...+b_{k - l}D ^{k - 1}, последний умножается на порождающий полином кода g(D) = g_o +g_lD+...+g_{n - k}D^{n - k}, и после приведения подобных членов определяются п коэффициентов полинома x(D), являющихся символами кодо­вого слова.

Из уравнения видно, что любой из полиномов x(D), соответствую­щих кодовым словам полиномиального кода, должен делиться без остатка на порождающий полином g(D). Остаток от деления полинома y(D), соответст­вующего принятой из канала комбинации, на порождающий полином кода g(D) называется синдромным полиномом s(D). Если синдромный полином равен нулю (т.е. деление произошло без остатка), то принятая комбинация является кодовым словом. В противном случае принятая комбинация не является кодо­вым словом. Таким образом, для полиномиальных кодов процедура обнаруже­ния ошибок (вычисление синдрома) состоит в делении принятой комбинации на порождающий многочлен.

На практике находят применение циклические коды, являющиеся частным случаем полиномиальных кодов.

Определение . Линейный двоичный (n, k)-код V называется циклическим кодом, если в результате циклического сдвига любой из его комбинаций полу­ченная комбинация снова принадлежит коду, т.е. S_x є V, если x є V.

Теорема. Для любого двоичного циклического (п, к)-кода существует такой многочлен g(D) степени r = n-k с двоичными коэффициентами, который делит без остатка многочлен Dⁿ +1, и при этом любое кодовое слово может быть пред­ставлено как многочлен х(D) степени n-1 следующего вида:

x(D) = g(D)b(D),

где b(D) — произвольный многочлен с двоичными коэффициентами степени не выше k- 1.

Многочлен g(D), о котором идёт речь в данной теореме, называется порож­дающим многочленом циклического кода.

Циклические коды значительно упрощают описание линейного кода, по­скольку для них вместо задания k х (n-k) элементов двоичной матрицы Р в представлении требуется задать (n-k+1) двоичных коэффициентов многочлена g(D). Кроме того, они упрощают процедуру кодирования и декоди­рования для обнаружения ошибок. Действительно, для осуществления кодиро­вания достаточно выполнить перемножение полиномов, что реализуется с по­мощью линейного регистра, содержащего k ячеек памяти и имеющего обрат­ные связи, соответствующие многочлену h(D).

Для обнаружения ошибок достаточно разделить многочлен, соответствующий принятому слову y(D), на порождающий многочлен g(D) и проверить, будет ли остаток от деления равен нулю. Эта процедура также осуществляется на линейных сдвиговых регистрах с обратными связями. Однако более важное преимущество циклических кодов состоит в том, что они могут быть сконструированы как коды с некоторым га­рантированным значением минимального кодового расстояния. Для этого не­обходимо определённым образом выбрать порождающий многочлен кода g(D). Циклические коды, которые имеют порождающий многочлен, заданный свои­ми определёнными корнями, называются кодами Боуза-Чоудхури-Хоквингема (кратко БЧХ-кодами). Однако корни этого многочлена ищутся не среди веще­ственных или комплексных чисел, а как элементы так называемых конечных полей Галуа.