Вероятность ошибочного декодирования

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

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

При приеме в целом
производится регистрация кодовых
сигналов. Под кодовым
сигналом
при этом
принимается вся последовательность
элементарных сигналов, составляющих
кодовую комбинацию.

Предположим, что
вероятность искажения отдельного
сигнала в кодовой комбинации равна
.
Будем полагать, что искажения различных
сигналов в кодовой комбинации статистически
независимые (что является справедливым
для каналов с постоянными параметрами
и флуктуационной помехой). Вероятность
того, что при поэлементном приеме
комбинация изn
элементов содержит равно

ошибок по
биномиальному закону, равна

,
(8.37)

где

— вероятность
искажения одного элемента кодовой
комбинации.

Вероятность
правильной регистрации кодовой комбинации
из n
элементов равна вероятности того, что
в ней содержится не более

ошибок

.

(8.38)

Число ошибок

и менее
исправляется кодом c
.

Тогда вероятность
ошибочного декодирования кодовой
комбинации

.
(8.39)

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

,
(8.40)

где
— количество информационных разрядов.

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

8.5. Блочные линейные коды

8.5.1. Математическое описание процессов кодирования и декодирования

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

Поле
,
состоящее из конечного числа элементовназываетсяконечным
полем
или полем
Галуа. Для
любого числа
,
являющегося степенью простого числа,
существует поле, насчитывающееэлементов. Поле не может содержать менее
двух элементов. Поле, включающее только
0 и 1, обозначим GF(2). Правила сложения и
умножения в поле с двумя элементами
представлены в табл. 8.11.

Таблица 8.11. Правила
сложения и умножения в поле с двумя
элементами

+	0	1		х	0	1
0	0	1	0	0	0
1	1	0	1	0	1

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

Обычно
,
где— некоторое целое число. Если,
линейные коды называются групповыми,
так как кодовые слова образуют
математическую структуру, называемую
группой. При формировании этого кода
линейной операцией является суммирование
по mod2.

При задании кода
обычно указывают, какие информационные
элементы принимают участие в формировании
каждого из k
проверочных разрядов. Например, для
кода с n=5,
m=3
и k=2
каждый проверочный разряд
определяется суммированием по модулю
2 по правилу

;

,

где
— информационные разряды. Комбинация
такого кода записывается в видеили в обратном.
При задании кода можно указать все
разрешенные для этого кода комбинации.
Для линейных кодов способ задания можно
значительно упростить. Дляm
информационных разрядов число всех
разрешенных кодовых комбинаций будет
равняться
.

Пусть
(табл.8.12). Так как в каждой кодовой
комбинации такого кода три информационных
элемента, то число возможных комбинаций
кода будет равно.

Проверочные
элементы формируются как сумма по модулю
два информационных элементов, а именно:

(8.41)

Так для кодовой
комбинации №4

в соответствии с
правилами суммирования по модулю 2.

Для задания кода
нет необходимости записывать в таблицу
все используемые комбинации данного
кода. Код может быть задан матрицей,
которая содержит один из возможных
наборов линейно независимых строк. Под
линейно независимыми кодовыми комбинациями
понимают такие, сумма по модулю 2 которых
(в любом сочетании) не равняется нулю.
Выберем из всех кодовых комбинаций
только линейно независимые. Так для
приведенного выше кода линейно
независимыми будут группы комбинаций:

1. 1 0 0 1 0 2. 0 1 0 1 1 3. 0 0 1 0 1	1. 1 0 0 1 0 4. 1 1 0 0 1 5. 0 1 1 1 0	1. 1 0 0 1 0 4. 1 1 0 0 1 7. 1 1 1 0 0
(1)	(2)	(3)

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

1. 1 0 0 1 0  2. 0 1 0 1 1 ——————— 1 1 0 0 1	1. 1 0 0 1 0  3. 0 0 1 0 1 —————— 1 0 1 1 1	2. 0 1 0 1 1  3. 0 0 1 0 1 ——————— 0 1 1 1 0	1. 1 0 0 1 0  2. 0 1 0 1 1  3. 0 0 1 0 1 ————- 1 1 1 0 0.
4.	5.	6.	7.

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

Таким образом,
любая из трех приведенных выше комбинаций
может быть порождающей для систематического
(5,3) кода с
.
В общем виде производящую матрицу из
строк истолбцов записывают так:

.
(8.42)

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

или
. (8.43)

где

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

Для рассматриваемого
примера – (5,3) кода каноническая форма
порождающей матрицы имеет вид

Из данного примера
видно, что первые три столбца составляют
единичную матрицу; четвертый столбец
указывает, что при формировании первого
проверочного разряда принимают участие
первый и второй информационные разряды.
Пятый столбец указывает, что при
формировании второго проверочного
разряда принимают участие второй и
третий информационные разряды.

Для

.
(8.44)

Затем выделяется
подматрица
являющаяся транспонированной матрицей:

если
то.
(8.45)

Затем полученной
матрице
справа приписывается единичная матрица
и получается проверочная матрицаН.

.
(8.46)

Проверочная матрица
очень удобна для определения места
ошибки в кодовой комбинации, а следовательно
и исправления ошибки.

Проверочная матрица
однозначно связана с порождающей
соотношением

,
(8.47)

Где умножение и
суммирование соответствующих элементов
матриц производится по модулю 2.

Пример.

Для порождающей
матрицы, G(5,3)
проверочная матрица имеет вид

Тогда

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

(8.48)

Процесс декодирования
математически описывают произведением
проверочной матрицы
и вектора – столбца, отображающего
принятую кодовую комбинацию,
где— вектор ошибки

,
(8.49)

где
– результат декодирования (синдром);

— знак транспортирования.

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

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

.
(8.50)

Если обозначить
-й
столбец проверочной матрицы, то

.

Вектор ошибки
содержит «1» на тех позициях, символы
на которых искажены. Пусть эти позиции
имеют номера,
тогда будет справедливо равенство

.
(8.51)

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

,

при любом сочетании
искаженных символов.

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

при
(для исправления одиночной ошибки);

при любых
и(для обнаружения пакета из двух ошибок);

при любых
и(для обнаружения пакета из трех ошибок).

Матрицы
иможно поменять ролями. Тогда матрицабудет порождающей, а— проверочной.

Коды, взаимосвязанные
между собой таким образом, называют
дуэльными (двойственными).

Соседние файлы в папке Пособие ТЕЗ_рус12

• #
• #
• #
• #
• #
• #
• #
• #
• #

1

— одна из возможных мер характеризации точности воспроизведения сообщений, передаваемых по каналу связи (см. также Сообщений точность воспроизведения). Пусть для передачи сообщения x, вырабатываемого источником сообщений и принимающего Мразличных возможных значений 1,. . ., М с распределением вероятностей р _m=Р{x=m}, m=l, , . . , M, используется нек-рый канал связи. Тогда для фиксированных методов кодирования и декодирования (см. также Информации передача).О. д. в. Р _{е, т}, m=1, . . ., М, определяется равенством

где — декодированное сообщение на выходе канала. Средней О. д. в. Р _е наз. величина

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

где нижняя грань берется по всевозможным методам кодирования и декодирования. Ввиду трудностей получения точного выражения для , связанных с тем обстоятельством, что в общем случае неизвестны оптимальные методы кодирования, интерес представляет изучение асимптотич. поведения при возрастании длительности передачи по каналу. Точнее, рассматривается следующая ситуация. Пусть для передачи используется отрезок длины N канала связи с дискретным временем и R=(ln M)/N. Требуется изучить асимптотич. поведение при и R=const (это означает, что длительность передачи возрастает, а ее скорость остается постоянной). Если рассматриваемый отрезок канала является отрезком однородного канала без памяти с дискретным временем и конечными пространствами Y и значений компонент сигналов на входе и выходе, то известны следующие верхние и нижние оценки :

(1)

где a(N) и b(N).стремятся к нулю с ростом N,aфункции E_r(R).и E_sp(R).определяются следующим образом:

(2)

(3) где

Здесь — произвольное распределение вероятностей на ,

,- компоненты сигналов на входе и выходе рассматриваемого канала без памяти. Известно, что E_r(R).и E_sp,(R), определяемые формулами (2) и (3), являются положительными, выпуклыми вниз, монотонно убывающими функциями от Rпри , где С — канала пропускная способность, причем E_r(R)=E_sp(R). при , здесь R_cr — величина, определяемая переходной матрицей канала и называемая критической скоростью для данного канала без памяти. Таким образом, для значений , главные члены верхней и нижней оценок (1) для асимптотически совпадают, откуда следует, что для этого диапазона изменения Rизвестно точное значение функции надежности канала Е(R), определяемой равенством

Для значении , точное значение E(R).для произвольных каналов без памяти неизвестно (1983), хотя оценки (1) и могут быть улучшены. Экспоненциальный характер убывания доказан для весьма широкого класса каналов.

Лит.:[1] Галлагер Р., Теория информации и надежная связь, пер. с англ., М., 1974; 12] Файнстейн А., Основы теории информации, пер. о англ., М., I960.

Р. Л. Добрушин, В. В. Прелов.

НАДЕ АППРОКСИМАЦИЯ — наилучшая рациональная аппроксимация степенного ряда. Пусть

(1)

— произвольный степенной ряд (формальный или сходящийся), — целые числа, R _п, _т — класс всех, рациональных функций вида р/q, где ри q — многочлены от . Аппроксимацией Паде типа ( п, т).ряда (1) (функции f) наз. рациональная функция , имеющая максимально возможный в классе R_n,m порядок касания с рядом (1) в точке z=0. Точнее, функция p _{п, т} определяется условием

где s(j) — индекс первого из отличных от нуля коэффициентов ряда

Функцию p _{п, т} можно определить также как отношение p _{п, т=}p/qлюбых многочленов , удовлетворяющих соотношениям

(2)

При фиксированных п, т существует единственная П. а. p _{п, т} ряда (1). Таблица наз. таблицей Паде ряда (1). Последовательности вида наз. строками таблицы Паде (нулевая строка совпадает с последовательностью многочленов Тейлора для f); — столбцами таблицы Паде; — диагоналями таблицы Паде. Наиболее важный частный случай f=0 — главная диагональ.

Вычисление функции p _{п, т} сводится к решению системы линейных уравнений, коэффициенты к-рых выражаются через коэффициенты f_k, k=0, l,. . ., n+m, заданного ряда. Если отличен от нуля определитель Ганкеля

то знаменатель q _{п, т} функции p _{п, т} определяется по формуле

(нормировка q _{п, т}(0)=1; явная формула может быть написана и для числителя функции p _{п, т}). При этом

Последнее соотношение иногда принимают за определение П. а.; в этом случае П. а. могут не существовать для нек-рых (n, т). Для обозначения П. а. типа ( п, т).заданного ряда f часто употребляется символ [n/m] = [n/m]_f.

Для эффективного вычисления П. а. удобнее пользоваться не явными формулами, а рекурентными соотношениями, существующими в таблице Паде. Разработано большое количество алгоритмов для машинного вычисления П. а.; эти вопросы имеют особенно важное значение в связи с приложениями (см. [17], [18]).

Впервые общую задачу об интерполяции заданных значений функции в n+m+1 различных точках посредством рациональной функции класса R _{п, т} рассмотрел О. Коши [1]; К. Якоби [2] распространил результаты О. Коши на случай кратных узлов интерполяции. Случай одного (n+m+1 )-кратного узла интерполяции соответствует П. а. Понятие П. а. сформировалось в кон. 19 в. в рамках классич. теории непрерывных дробей (Г. Фробениус [3], А. Паде [4]). Фундаментальные результаты о диагональных П. а. были получены П. Л. Чебышевым, А. А. Марковым, Т. Стильтьесом (Т. Stieltjes) в терминах непрерывных дробей; ими были обнаружены и исследованы связи диагональных П. а. с ортогональными многочленами, квадратурными формулами, проблемой моментов и другими вопросами классич. анализа (см. [7] — [9]). Начало изучению строк таблицы Паде было положено работами о радиусах мероморфности функции, заданной степенным рядом, и о сходимости строк таблицы Паде в кругах мероморфности (см. [5], [6]).

С нач. 20 в. П. а. становятся самостоятельным объектом анализа и составляют важную главу теории рациональных приближений аналитич. ций. Используя для своего построения локальные данные (коэффициенты степенного ряда), они позволяют изучать глобальные свойства соответствующей аналитич. ции (аналитич. продолжение, характер и расположение особенностей и т. п.) и вычислять значение функции за пределами круга сходимости степенного ряда.

Наряду с классическими П. а. рассматриваются различные их обобщения: общие процессы интерполяции посредством рациональных функций со свободными полюсами (многоточечные аппроксимации Паде); рациональные аппроксимации рядов по заданной системе многочленов (напр., по ортогональным многочленам); совместные П. а. (аппроксимации Паде — Эрмита); рациональные аппроксимации (типа П. а.) степенных рядов от нескольких переменных и др.

Лит.:[1] Саuсhу A.-L., Cours d’analyse de I’Ecole royale polyteclmique, pt. 1- Analyse algebrique, P., 1821; [2] Jacobi C. G. J., «J. reine und angew. Math.», 1846, Bd SO, S. 127-56; [3] Frоbenius G., там же, 1881, Bd 90, S. 1 — 17; [4] Pade H., «Ann. scient. Ecole norm, super.», 1892, t. 9, p. 1-93; [5] Hadamard J., «J. math, pures et appl.», 1892, t. 8, p. 101-86; [6] Mоntessus deBalloreB.de, «Bull. Soc. math. France», 1902, t. 3(1, p. 28-36; [7] Чебышев П. Л., Полн. собр. соч., т. 3, М.- Л., 1948; [8] Марков А. А., Избр. труды по теории непрерывных дробей и теории функций, наименее уклоняющихся от нуля, М.- Л., 1948; [9] Стилтьес Т., Исследования о непрерывных дробях, пер. с франц., Хар.- К.. 1936; [10] Wall H. S., Analytic theory of continued fractions, Toronto — N. Y,- L., 1948; [11] Perron O., Die Lehre von den Kettenbruchen, 3 Aufl., Bd 2, Stuttg., 1957; [12] The Fade approximant in theoretical physics, N. Y.- L., 1970; [13] Pade approximants and their applications, L.-N. Y., 1973; [14]

Pade approximants method and its applications to mechanics, В.- Hdlb.- N. Y., 1976; [15] В a k e r G. A., Essentials of Fade approximants, N. Y.- San Franc.- L., 1975; [16] Fade and rational approximation, N. Y.- [a. o.], 1977; [17] Gilewicz J., Approximants dc Pade, В.- Hdlb.- N. Y., 1978; [18] Pade approximation and its applications, В.- Hdlb.- N. Y., 1979.

В. А. Рахманов.

Презентация на тему: » Помехоустойчивое кодирование Вероятность ошибочного декодирования.» — Транскрипт:

---

---