Галкин В.А. - Методическое пособие по выполнению домашнего задания по дисциплине «Основы телекоммуникаций»

Московский государственный технический университет им. Н.Э. Баумана

Кафедра «Системы обработки информации и управления»

Методическое пособие

по выполнению домашнего задания по дисциплине

«Основы телекоммуникаций»

Москва - 2008

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

Постановка задачи.

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

Обнаруживающая способность кода C_о определяется как отношение числа обнаруженных ошибок N_o к общему числу ошибок данной кратности, которое определяется как число сочетаний из n (длина кодовой комбинации) по i (кратность ошибки – число единиц в векторе ошибок) - Cⁱ_n.

C_о = N_o / Cⁱ_n (1)

Корректирующая способность кода C_k определяется как отношение числа исправленных ошибок N_k к общему числу ошибок данной кратности, которое определяется как число сочетаний из n (длина кодовой комбинации) по i (кратность ошибки – число единиц в векторе ошибок) - Cⁱ_n .

C_k = N_k / Cⁱ_n (2)

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

Таблица 1.

Вопросы из теории.

Циклические коды.

Кодирование циклическим кодом:

Этапы:

1. Задана информационная последовательность m(x). Умножить заданный полином степени (k - 1) на х^(n-k), т.е. сдвинуть в сторону старших разрядов на (n – k); где n = r+k, r – степень образующего полинома , k – число информационных разрядов данной последовательности;

2. Получить остаток от деления полинома x^(n-k)*m(x) на g(x) – образующий полином. Степень остатка <= n – k – 1.

3. Объединить остаток р(х) и исходный полином x^(n-k)*m(x) для получения кодового слова; x^(n-k)*m(x) @ p(x), где @ - конкатенация;

Декодирование циклического кода:

V(x) – передаваемый кодовый полином; r(x) – принятый;

r(x)=g(x)*q(x)+S(x), где q(x) – частное, S(x) – остаток от деления принятого полинома на порождающий полином (если S(x) = 0, ошибки нет или она не обнаружена).

r(x)=V(x)+e(x), где e(x) – вектор ошибки;

e(x)=V(x)+q(x)*g(x)+S(x) или e(x)=[ m(x)+q(x)]*g(x)+s(x),

т.е. синдром ошибки s(x) есть остаток от деления вектора ошибки на порождающий полином.

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

Для различных сочетаний одиночных ошибок в кодовой комбинации двоичного циклического [7,4]-кода соответствующие им синдромы представлены в таблице 2. Рассмотрим пример двоичного циклического [7,4]-кода (n=7, k=4). Порождающий полином такого кода является примитивный полином степени (n-k): g(x) = x³ + x + 1 .

Таблица 2.

Пример.

Пусть нам необходимо закодировать кодовый вектор с k=4 1101. Представим его в виде полинома степени (k-1): m(x) = x³ + x² + 1.

Кодирование.
1. Умножаем m(x) на (x^n-k) : m(x)•x³ = (x³ + x² + 1)•x³ = x⁶ + x⁵ + x³ , что соответствует сдвигу кодового вектора в сторону старших разрядов на (n-k) разряда и добавлению в освободившиеся разряды нулей: 1101000.

2. Делим m(x)•x³ на g(x):

    или    

Таким образом, остаток: p(x) = p₀.

3. Приписываем остаток к информационным разрядам: v(x) = m(x)•x^n-k + p(x) = x⁶ + x⁵ + x³ + 1, или выполняем операцию конкатенации исходного кодового вектора и вектора остатка: 1101.001, в результате получаем циклический (7,4)-код.

Декодирование.
Пусть вектор ошибки равен e(x) = x⁴, тогда принятый полином будет иметь вид:
r(x) = v(x) + e(x) = x⁶ + x⁵ + x⁴ + x³ + 1 или 1101001+0010000=1111001

Для обнаружения ошибки необходимо разделить принятый полином на порождающий:

    или    

По виду синдрома из таблицы 2.3 определяем место ошибки – разряд с весом 4.

Коды Хэмминга.

К корректирующим кодам относятся коды Хэмминга с кодовым расстоянием d=3.

Для кодов Хэмминга выбрано предельное значение разрешенных кодовых комбинаций N = 2ⁿ•(1+n)^-1, а число информационных разрядов (k) определится как:

k = log[ 2ⁿ•(1+n)^-1 ] = n - log(n + 1). (3)

Данное уравнение имеет целочисленные решения k = 0,1,4,11,26,…., которые и определяют соответствующие коды Хэмминга [3,1] - код, [7,4] - код, [15,11] - код и т.д. Рассмотрим алгоритмы кодирования и декодирования на примере [7,4] - кода Хэмминга.

Алгоритм кодирования.
Все номера позиций кода нумеруются в двоичной системе счисления, начиная с единицы (p)-разрядным двоичным числом: p = [ log(n) ], где [ ] - ближайшее большее целое, (n) - число разрядов кода c_nc_n-1 ...c_j...c₁.

Проверочные разряды размещаются в позициях кода, кратных целой степени двойки 2⁰,2¹, … и т.д.: c_j = b_j , j = 2ⁱ, i = 0,1,…,(r-1), где (r) - число проверочных разрядов.

Значение c_j проверочного разряда определяется как сумма по mod2 тех разрядов кода, в номере которых двоичный разряд с (i)-ым весом равен единице.

Пример.
Пусть информационный кодовый вектор v = 1101. В коде Хэмминга этот вектор будет занимать позиции c₃,c₅,c₆ и c₇, начиная с младшего разряда, а позиции c₁,c₂,c₄ отводятся под проверочные разряды кода. Пронумеруем все позиции кода в двоичной системе счисления: c₁₁₁c₁₁₀c₁₀₁[c₁₀₀]c₀₁₁[c₀₁₀][c₀₀₁] и выделим позиции для размещения проверочных разрядов. Определим значения проверочных разрядов кода суммированием по mod2 тех разрядов кода, в номере которых двоичный разряд с (i)-ым весом равен единице.

(4)

Таким образом, получен кодовый вектор v' = 1100110, который передается по каналу, подверженному влиянию помех. Пусть вектор ошибки равен e = 0000100 , тогда принятая из дискретного канала кодовая комбинация будет иметь вид:

v'' = 1100010 = v' e. (5)

Алгоритм декодирования.
Вычисляется значение синдрома ошибки:

E_ош = || h_rh_r-1 ...h_i...h₁ ||. (6)

Значение (i)-го разряда синдрома определяется как сумма по mod2 тех разрядов принятого кода, включая проверочные, в номере которых вес двоичного разряда совпадает с весом разряда синдрома.

(7)

Для нашего примера v'' = 1100010

(8)

E_ош = || h₃h₂h₁ || = ||011|| - синдром ошибки определяет в двоичной системе номер разряда, в котором обнаружена однократная ошибка.

Для исправления ошибки необходимо инвертировать третий разряд - c₃. Получим: v'' = 1100110, откуда, выделяя информационные разряды, получаем исходный кодовый вектор v = 1101.

Требования к выполнению домашнего задания.

Отчет о выполнении ДЗ должен содержать:

1. Постановку и метод решения задачи для варианта задания.

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

3. Заполненную таблицу 1.

4. Выводы.

5. Список используемой литературы и URL-ссылок.

6. Электронную копию отчета и программы (включая исходные модули).

Литература.

1. Галкин В.А., Григорьев Ю.А. Телекоммуникации и сети: Учеб. Пособие для вузов.-М.: Изд-во МГТУ им.Н.Э.Баумана, 2003

2. http://www.opennet.ru/docs/RUS/inet_book/

Варианты задания

Обозначения: