Из уравнения (6,а.1) следует, что дополнительные символы связаны с информационными символами соотношением 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Из уравнения (6,а.1) следует, что дополнительные символы связаны с информационными символами соотношением



і = k +1, k +2,…, n. (6,а.3)

Здесь сложение производится по модулю 2. Таким образом, элементы і -го столбца порождающей матрицы определяют і -ый дополнительный символ.

Строки матрицы G должны удовлетворять следующим условиям [2, с.86…88].

1. Расстояние между любыми двумя строками не должно быть меньше d.

2. Каждая строка должна содержать не менее d единиц.

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

Последнее условие для матрицы (6,а.2) выполняется благодаря тому, что первые k столбцов образуют единичную матрицу. Следовательно, при построении матрицы-дополнения необходимо удовлетворить условия 1 и 2.

2.4 Если кодовое расстояние d = 3, то условия 1 и 2 для строк матрицы-дополнения можно сформулировать так.

1 Расстояние между любой парой строк должно быть не меньше 1 (т.е. достаточно, чтобы строки были несовпадающими.).

2 Каждая строка должна содержать не менее двух единиц.

Поскольку эти условия легко выполнимы, то и порождающая матрица рассматриваемого кода (n, k) может быть легко построена.

Например, для кода (7, 4) порождающая матрица имеет вид [1,ф-ла (5.23)]

G . (6,а.4)

2.5 Процесс декодирования включает в себя вычисление синдрома, который в матричной форме записывается как:

= C, (6,а.5)

где H – проверочная матрица размером r ´ n.

– матрица – столбец размера n, соответствующая принятой из канала кодовой комбинации;

C –матрица – столбец размера r.

Из соотношения 6,а.5) следует, что вычисление синдрома сводится к r проверкам

i = 1, 2, …, r, (6,а.6)

т.е. i -ая проверка определяется элементами i -ой строки проверочной матрицы.

2.6 Проверочная матрица строится следующим образом [2, с. 88]. В начале строится матрица, транспонированная по отношению к матрице- дополнению, а затем к ней справа приписывается единичная матрица:

H . (6,а.7)

Например, для кода (7.4) с порождающей матрицей (6,а.4) проверочная матрица имеет вид:

H , (6,а.8)

и проверки декодера сводятся к следующим выражениям:

с 1 = , с 2 = , с 3 = .

На основе (6,а.9) легко составить таблицу ненулевых синдромов (табл. 6,а.1).

Таблица 6,а.1 – Ненулевые синдромы кода Хэмминга (7, 4)

Синдром с1с2с3              
Ошибочный символ

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

2.7 Правило формирования дополнительных символов (6,а.3) является основой алгоритма работы кодера:

1. На вход кодера поступают k информационных символов в параллельном коде либо в последовательном коде (в последнем случае требуется регистр сдвига длиной k).

2. Вычисляются r = nk дополнительных символов с помощью сумматоров по модулю r.

3. k информационных и r дополнительных символов поступают на выход кодера в параллельном либо последовательном коде (в последнем случае требуется преобразователь параллельного кода в последовательный).

На рис. 6,а.1 приведена функциональная схема кодера кода (7, 4) с порождающей матрицей (6,а.4). Символы входной и выходной кодовых комбинаций представлены в параллельном коде.

2.8 Алгоритм работы декодера следующий:

1. На вход декодера поступает n символов принятой кодовой комбинации.

2. На основе соотношения (6,а.6) вычисляется синдром.

3. Анализатор синдрома, построенный на основе таблицы синдромов, формирует сигналы для исправления ошибочных информационных символов.

4. Производится исправление ошибочных символов, состоящее в их инверсии и выполняемое путем сложения по модулю 2 исправляемого символа с единицей (пусть – некоторый символ, тогда Å 1 = ).

5. На выход декодера после исправления ошибки поступает комбинация простого кода из k символов.

На рис. 6,а.2 приведена функциональная схема декодера кода (7, 4), построенная на основе проверочной матрицы (6,а.8). Символы входной и выходной кодовых комбинаций представлены в параллельном коде. Анализатор синдрома реализует следующую функциональную зависимость (табл. 6,а.2), построенную на основе таблицы синдромов (табл. 6,а.1).

 

 

Таблица 6,а.2 – Функциональная зависимость анализатора синдрома

Входы Выходы
С1 С2 С3          
               
               
               
               

2.9 Код, кодер и декодер которого строятся на многовходных сумматорах по модулю 2, называют кодом Хэмминга или кодами с проверками на четность. Основы построения кодеров и декодеров кодов Хэмминга рассмотрены выше и иллюстрированы на примере кода (7, 4). Используя изложенные принципы можно построить кодер и декодер при других значениях n и k.

3 Ключевые вопросы

3.1 Дайте определение корректирующих кодов.

3.2 Что такое кодовое расстояние?

3.3 Запишите соотношения, определяющие корректирующую способность кода по заданному кодовому расстоянию.

3.4 Дайте определение систематических корректирующих кодов.

3.5 Как определить число дополнительных символов при заданном k, если d = 3?

3.6 Что такое порождающая матрица?

3.7 Как построить порождающую матрицу для систематического кода?

3.8 Что такое проверочная матрица?

3.9 Что такое синдром?

3.10 Поясните принцип построения декодера кода Хэмминга.

4 Домашнее задание

4.1 Изучить разд. 2 пособия.

4.2 Код (7, 4) задан порождающей матрицей

 

G = .

Записать номер Вашего стенда N в двоичной системе счисления. Считая, что номер – четырехзначная комбинация на входе кодера, рассчитать комбинацию на выходе кодера. Составить проверочную матрицу заданного кода. Составить таблицу синдромов заданного кода. Ввести однократную ошибку в символ bN сформированной комбинации, рассчитать синдром для получения комбинации. Убедится, что синдром соответствует ошибочному символу .

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

5 Лабораторное задание

5.1 Ознакомление с виртуальным макетом.

Запустить программу на компьютере и, управляя курсором мышью, освоить ввод информационных символов, управление работой кодера и декодера, ввод ошибок.

5.2 Исследование процесса кодирование.

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



Поделиться:


Последнее изменение этой страницы: 2017-01-24; просмотров: 371; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.144.81.21 (0.051 с.)