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×n двоичную матрицу G, которая называется порождающей матрицей кода:

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

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

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

Любая (k х n) двоичная матрица G с линейно-независимыми строками может быть приведена к каноническому виду

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

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

где с = bР.

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

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

Коды с общей проверкой на чётность.Это класс кодов с параметрами (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).

Для обнаружения ошибок достаточно разделить многочлен, соответствующий принятому слову y(D), на порождающий многочлен g(D)и проверить, будет ли остаток от деления равен нулю.

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