4.3 Кодирование в дискретном канале с шумом

Теоремы Шеннона о кодировании в дискретном канале с шумом. Дискретным каналом с шумом называется канал, в кото­ром сигналы А(t) и В(t) (см. рис. 4.1.1) являются последова­тельностями символов, однозначная связь между входными и выходными сигналами отсутствует, и поэтому передача сим­волов в канале сопровождается случайными ошибками.

Ответ на вопрос о возможности безошибочной передачи информации дается теоремами Шеннона о кодировании в дискретных каналах с шумом.

Первая и вторая теоремы. Если скорость созда­ния информации Н источником на входе шумящего канала без памяти с пропускной способностью С меньше пропускной способности, то существует такой код, при котором вероят­ность ошибок на приемном конце сколь угодно мала, а ско­рость передачи информации сколь угодно близка к скорости ее создания.

Обратная теорема. Если Н > С, то никакой код не сможет сделать вероятность ошибок сколь угодно малой и достигнуть ненадежности, меньшей чем Н-С.

Основной способ повышения помехоустойчивости системы передачи информации – это разумное введение избыточности в передаваемый сигнал А(t).

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

Пусть а₁, а₂, ... , а_s – двоичные кодовые слова длиной в n символов каждое, соответствующие s буквам алфавита источника. Каждое кодовое слово можно формально рассмат­ривать как вектор-строку, соответствующий некоторой точке в n-мерном пространстве.

Расстояние Хэмминга d_jk между двумя кодовыми сло­вами а_j и а_k равно числу символов, в которых эти слова отли­чаются одно от другого.

У

Таблица 4.3.1

0 0=0	0 1=1
1 0=1	1 1=1

добно вычислять расстояние между двумя кодовыми сло­вами, пользуясь операцией суммирования по модулю 2. Пра­вила cложения сведены в таблице 4.3.1, где – знак операции суммирования по модулю 2.

Сложение и вычитание по модулю 2 эквивалентны.

Расстояние между двумя кодовыми словами можно теперь определить как количество единиц в кодовом слове, получен­ном при суммировании этих слов по модулю 2.

Наименьшее значение расстояния между словами в вы­бранной системе кодирования называется кодовым рас­стоянием d_код.

Считают, что в канале произошла q-кратная ошибка, если кодовое слово на выходе канала отличается от кодового сло­ва на его входе ровно в q символах (т.е. расстояние между этими словами-векторами равно q). Таким образом, вектор на выходе канала равен сумме по модулю 2 входного вектора и вектора ошибки.

Код позволяет обнаруживать любую ошибку кратности q_о, если его кодовое расстояние удовлетворяет условию

.

(4.3.1)

Код позволяет исправлять любую ошибку крат­ности q_и, если выполняется условие

.

(4.3.2)

Линейные блочные коды. Среди всех корректирующих кодов наибольшее примене­ние нашли линейные блочные коды. Это – двоичный корректирующий (n,k)-код, удовлетвор­яющий следующим требованиям:

1) Все кодовые слова содержат по n символов, из которых k символов – информационные, а остальные n-k символов – проверочные.

2) Сумма по модулю 2 любых двух кодовых слов снова дает кодовое слово, принадлежащее этому же коду.

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

Следующим этапом в построении линейного блочного кода является определение проверочной матрицы Н, имеющей r=n-k строк и n столбцов. Любой вектор-строка прове­рочной матрицы Н ортогонален любому вектору-строке про­изводящей матрицы G, следовательно,

GH^T=0,

(4.3.3)

где H^T – транспонированная матрица H.

Заметим, что два вектора u=u₁,...,u_n и v=v₁,...,v_n являются, по опреде­лению, ортогональными, если

.

Работа кодера для (n,k)-кода заключается в том, что к поступающему на его вход k-разрядному вектору информаци­онных символов x он должен добавить r проверочных симво­лов. Правило образования кодового слова а определяется со­отношением

a=xG.

(4.3.4)

Умножив обе части этого выражения справа на H^T и учитывая (4.3.3), получим другое соотношение, определяющее функции кодера

а H^T =0,

(4.3.5)

т.е. он должен добавлять r проверочных символов таким об­разом, чтобы любой из получаемых в итоге кодовых векто­ров а удовлетворял соотношению (4.3.5).

Один из способов декодирования принятого вектора b пре­дусматривает вычисление r-разрядного исправляющего вектора (синдрома) с по правилу

с=bH^T.

(4.3.6)

Из формулы (4.3.5) следует, что значение синдрома опреде­ляется только вектором ошибки. Если с 0, делают заключе­ние о наличии ошибки (обнаружение ошибки). Так как раз­личным ошибкам кратности q_и, удовлетворяющей неравенст­ву (4.3.2), соответствуют различные значения синдрома, то вычисленное значение синдрома с однозначно определяет положение сим­волов, в которых произошли такие ошибки. Эти ошибки ис­правляются в декодере суммированием принятого вектора b с соответствующим вектором ошибок.

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

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

Код Хэмминга имеет кодовое расстояние, равное трем, и полностью харак­теризуется числом проверочных символов r. Общее число символов в кодовом слове равно n=2^r-1. В качестве столб­цов проверочной матрицы Н выбираются всевозможные r-разрядные двоичные числа, исключая число нуль.

Код Рида-Малера полностью характеризуется двумя це­лыми положительными числами: m≥З и δ<m. Число δ назы­вается порядком кода. Остальные параметры кода определя­ются из соотношений:

(4.3.7)

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

Циклический код полностью определяется первой строкой производящей матрицы G. Остальные строки получают в ре­зультате циклического сдвига первой строки на 1,2,...,k-1 элементов. Таким же циклическим свойством обладает и про­верочная матрица Н.

Более удобным является общепринятое описание кодовых комбинаций циклического кода при помощи полиномов. Кодовой комбинации v=(v₀,v₁,…,v_n-1) соответствует полином

v(x)= v₀x⁰+ v₁x¹+,…,v_n-1x^n-1. Способы кодирования и декодирования для конкретного кода полностью определяются, если задать производящий полином g(x)=1+g₁x+ g₂x²+…+ g_r-1x^r-1+x^r.

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