Методическое пособие
«Основы телекоммуникаций»
| Разработал к.т.н., доцент Галкин В.А. |
Москва - 2008
Целью домашнего задания является приобретение и закрепление студентами практических навыков по разработке и реализации алгоритмов кодирования и декодирования корректирующим кодом, а также определение реальной обнаруживающей или корректирующей способности этого кода.
Постановка задачи.
Имеется дискретный канал связи, на вход которого подается закодированная в соответствии с вариантом задания кодовая последовательность. В канале возможны ошибки любой кратности. Вектор ошибки может принимать значения от единицы в младшем разряде до единицы во всех разрядах кодового вектора. Для каждого значения вектора ошибки на выходе канала после декодирования определяется факт наличия ошибки и предпринимается попытка ее исправления.
Обнаруживающая способность кода Cо определяется как отношение числа обнаруженных ошибок No к общему числу ошибок данной кратности, которое определяется как число сочетаний из n (длина кодовой комбинации) по i (кратность ошибки – число единиц в векторе ошибок) - Cin.
Cо = No / Cin (1)
Корректирующая способность кода Ck определяется как отношение числа исправленных ошибок Nk к общему числу ошибок данной кратности, которое определяется как число сочетаний из n (длина кодовой комбинации) по i (кратность ошибки – число единиц в векторе ошибок) - Cin.
Ck = Nk / Cin (2)
В каждом варианте задания необходимо определить либо обнаруживающую, либо корректирующую способность кода. Результаты работы программы представить в виде таблицы:
Таблица 1.
| i | Cin | No или Nk | Cо или Ck | Примечание |
Вопросы из теории.
Циклические коды.
Кодирование циклическим кодом:
Этапы:
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) = x3 + x + 1.
Таблица 2.
| Ошибка e (x) | Синдром s(x) | Вектор синдрома | ||
| s3 | s2 | s1 | ||
| x0 | x0 | |||
| x1 | x1 | |||
| x2 | x2 | |||
| x3 | x + 1 | |||
| x4 | x2 + x | |||
| x5 | x2 + x + 1 | |||
| x6 | x2 + 1 |
Пример.
Пусть нам необходимо закодировать кодовый вектор с k=4 1101. Представим его в виде полинома степени (k-1): m(x) = x3 + x2 + 1.
Кодирование.
1. Умножаем m(x) на (xn-k): m(x)•x3 = (x3 + x2 + 1)•x3 = x6 + x5 + x3, что соответствует сдвигу кодового вектора в сторону старших разрядов на (n-k) разряда и добавлению в освободившиеся разряды нулей: 1101000.
2. Делим m(x)•x3 на g(x):
или 
Таким образом, остаток: p(x) = p0.
3. Приписываем остаток к информационным разрядам: v(x) = m(x)•xn-k + p(x) = x6 + x5 + x3 + 1, или выполняем операцию конкатенации исходного кодового вектора и вектора остатка: 1101.001, в результате получаем циклический (7,4)-код.
Декодирование.
Пусть вектор ошибки равен e(x) = x4, тогда принятый полином будет иметь вид:
r(x) = v(x) + e(x) = x6 + x5 + x4 + x3 + 1 или 1101001+0010000=1111001
Для обнаружения ошибки необходимо разделить принятый полином на порождающий:
или 
По виду синдрома из таблицы 2.3 определяем место ошибки – разряд с весом 4.
Коды Хэмминга.
К корректирующим кодам относятся коды Хэмминга с кодовым расстоянием d=3.
Для кодов Хэмминга выбрано предельное значение разрешенных кодовых комбинаций N = 2n•(1+n)-1, а число информационных разрядов (k) определится как:
k = log[ 2n•(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) - число разрядов кода cncn-1...cj...c1.
Проверочные разряды размещаются в позициях кода, кратных целой степени двойки 20,21, … и т.д.: cj = bj, j = 2i, i = 0,1,…,(r-1), где (r) - число проверочных разрядов.
Значение cj проверочного разряда определяется как сумма по mod2 тех разрядов кода, в номере которых двоичный разряд с (i)-ым весом равен единице.
Пример.
Пусть информационный кодовый вектор v = 1101. В коде Хэмминга этот вектор будет занимать позиции c3,c5,c6 и c7, начиная с младшего разряда, а позиции c1,c2,c4 отводятся под проверочные разряды кода. Пронумеруем все позиции кода в двоичной системе счисления: c111c110c101[c100]c011[c010][c001] и выделим позиции для размещения проверочных разрядов. Определим значения проверочных разрядов кода суммированием по mod2 тех разрядов кода, в номере которых двоичный разряд с (i)-ым весом равен единице.
| c111 | c110 | c101 | c100 | c011 | c010 | c001 |
(4)
Таким образом, получен кодовый вектор v' = 1100110, который передается по каналу, подверженному влиянию помех. Пусть вектор ошибки равен e = 0000100, тогда принятая из дискретного канала кодовая комбинация будет иметь вид:
v'' = 1100010 = v' 
e. (5)
Алгоритм декодирования.
Вычисляется значение синдрома ошибки:
Eош = || hrhr-1...hi...h1 ||. (6)
Значение (i)-го разряда синдрома определяется как сумма по mod2 тех разрядов принятого кода, включая проверочные, в номере которых вес двоичного разряда совпадает с весом разряда синдрома.
(7)
Для нашего примера v'' = 1100010
(8)
Eош = || h3h2h1 || = ||011|| - синдром ошибки определяет в двоичной системе номер разряда, в котором обнаружена однократная ошибка.
Для исправления ошибки необходимо инвертировать третий разряд - c3. Получим: v'' = 1100110, откуда, выделяя информационные разряды, получаем исходный кодовый вектор v = 1101.
Требования к выполнению домашнего задания.
Отчет о выполнении ДЗ должен содержать:
- Постановку и метод решения задачи для варианта задания.
- Алгоритмы кодирования, реализации модели канала связи, декодирования, вычисления обнаруживающей или корректирующей способности кода для ошибок всех возможных кратностей.
- Заполненную таблицу 1.
- Выводы.
- Список используемой литературы и URL-ссылок.
- Электронную копию отчета и программы (включая исходные модули).
Литература.
- Галкин В.А., Григорьев Ю.А. Телекоммуникации и сети: Учеб. Пособие для вузов.-М.: Изд-во МГТУ им.Н.Э.Баумана, 2003
- https://www.opennet.ru/docs/RUS/inet_book/
Варианты задания
| № варианта | Информационный вектор | Код | Способность кода |
| Ц [7,4] | Co | ||
| Ц [7,4] | Ck | ||
| Ц [15,11] | Co | ||
| X [7,4] | Ck | ||
| Ц [15,11] | Ck | ||
| X [7,4] | Co | ||
| X [15,11] | Co | ||
| X [15,11] | Ck | ||
| Ц [7,4] | Co | ||
| Ц [7,4] | Ck | ||
| Ц [15,11] | Co | ||
| X [7,4] | Ck | ||
| Ц [15,11] | Ck | ||
| X [7,4] | Co | ||
| X [15,11] | Co | ||
| X [15,11] | Ck | ||
| Ц [7,4] | Co | ||
| Ц [7,4] | Co | ||
| Ц [7,4] | Ck | ||
| Ц [15,11] | Co | ||
| X [7,4] | Ck | ||
| Ц [15,11] | Ck | ||
| X [7,4] | Co | ||
| X [15,11] | Co | ||
| X [15,11] | Ck | ||
| Ц [7,4] | Co | ||
| Ц [7,4] | Ck | ||
| Ц [15,11] | Co | ||
| X [7,4] | Ck | ||
| Ц [15,11] | Ck |
Обозначения:
Ц[7,4] – Циклический код g(x) = х3 + х + 1
Ц[15,11] – Циклический код g(x) = х4+ х + 1
X[7,4], Х[15,11] – коды Хэмминга
Co - обнаруживающая способность кода
Ck - корректирующая способность кода