Галкин В.А. - Методическое пособие по выполнению домашнего задания по дисциплине «Основы телекоммуникаций» (1071260)
Текст из файла
Московский государственный технический университет им. Н.Э. Баумана
Кафедра «Системы обработки информации и управления»
Методическое пособие
по выполнению домашнего задания по дисциплине
«Основы телекоммуникаций»
| Разработал к.т.н., доцент Галкин В.А. |
Москва - 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 | 0 | 0 | 1 |
| x1 | x1 | 0 | 1 | 0 |
| x2 | x2 | 1 | 0 | 0 |
| x3 | x + 1 | 0 | 1 | 1 |
| x4 | x2 + x | 1 | 1 | 0 |
| x5 | x2 + x + 1 | 1 | 1 | 1 |
| x6 | x2 + 1 | 1 | 0 | 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 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
(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
-
http://www.opennet.ru/docs/RUS/inet_book/
Варианты задания
| № варианта | Информационный вектор | Код | Способность кода |
| 1 | 1010 | Ц [7,4] | Co |
| 2 | 1101 | Ц [7,4] | Ck |
| 3 | 00001010001 | Ц [15,11] | Co |
| 4 | 1010 | X [7,4] | Ck |
| 5 | 00001010011 | Ц [15,11] | Ck |
| 6 | 1110 | X [7,4] | Co |
| 7 | 10101010011 | X [15,11] | Co |
| 8 | 01010101100 | X [15,11] | Ck |
| 9 | 0010 | Ц [7,4] | Co |
| 10 | 0001 | Ц [7,4] | Ck |
| 11 | 1011010001 | Ц [15,11] | Co |
| 12 | 0011 | X [7,4] | Ck |
| 13 | 00001010011 | Ц [15,11] | Ck |
| 14 | 1000 | X [7,4] | Co |
| 15 | 10101010100 | X [15,11] | Co |
| 16 | 01010101111 | X [15,11] | Ck |
| 17 | 0111 | Ц [7,4] | Co |
| 18 | 1000 | Ц [7,4] | Co |
| 19 | 1001 | Ц [7,4] | Ck |
| 20 | 11111010001 | Ц [15,11] | Co |
| 21 | 1011 | X [7,4] | Ck |
| 22 | 11111010011 | Ц [15,11] | Ck |
| 23 | 1110 | X [7,4] | Co |
| 24 | 11101010011 | X [15,11] | Co |
| 25 | 00010101100 | X [15,11] | Ck |
| 26 | 0100 | Ц [7,4] | Co |
| 27 | 0101 | Ц [7,4] | Ck |
| 28 | 10111111001 | Ц [15,11] | Co |
| 29 | 1111 | X [7,4] | Ck |
| 30 | 11111110011 | Ц [15,11] | Ck |
Обозначения:
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
