Задание на курсовую работу 2 Министерство связи Российской Федерации Санкт-Петербургский Государственный Университет Телекоммуникаций имени профессора М.А. Бонч-Бруевича по дисциплине “Компьютерные Системы Передачи Данных” преподаватель Федотова Л.В. выполнил Крайнов М.А. группа СК-76 Санкт-Петербург 2ooo год Содержание Заглавие Лист 1. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ 2 1.1. Введение 2 1.2. Исходные данные 2 2. ХАРАКТЕРИСТИКА СИСТЕМЫ РОС-НП 3 3. ОБЩАЯ ХАРАКТЕРИСТИКА КОДОВ, ПРИМЕНЯЕМЫХ В ПДС 6 3.1. Принцип построения корректирующих кодов 6 3.2. Классификация и характеристики корректирующих кодов 6 3.3. Циклические коды 7 4. Анализ возможностей заданного циклического кода 8 4.1. Составление порождающей матрицы и матрицы проверок 8 4.2. Определение минимального кодового расстояния 8 4.3. Составление таблицы всех разрешенных кодовых комбинаций и определение их веса 9 4.4. Определение доли необнаруженных ошибок 10 5. Расчет эффективности заданного циклического кода 11 5.1. Канал с независимыми ошибками. 11 5.2. Канал с группированием ошибок. 11 6. Выбор оптимальной длины циклического кода 12 7. Разработка программы 13 7.1. Обзор методов программной реализации 13 7.2. Описание программы 14 7.3. Листинг программы 15 1. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ. 1.1. Введение. Корректирующие коды могут использоваться в системах с обратной и без обратной связи (ОС). В системах с ОС корректирующие коды используются в режиме обнаружения ошибок. Иногда в системах без ОС допускается режим обнаружения ошибок. При обнаружении ошибок в кодовой комбинации она не выдаётся получателю. При этом считается что лучше получателю выдать сигнал стирания, нежели неправильный символ. Система может быть с решающей обратной связью (РОС) и с информационной обратной связью (ИОС). В данном курсовом проекте будет разрабатываться кодирующее устройство системы РОС-НПбл . Целью данной курсовой работы является самостоятельная разработка кодирующего устройство системы РОС-НПбл , составление и реализация на ЭВМ алгоритма и программы кодирования и декодирования циклического кода (n,k) с образующим полиномом P(x), а также экспериментальная проверка правильности программы. 1.2. Исходные данные (Вариант 8). 1. Задан обнаруживающий ошибки циклический код n,k = (15,5). n – количество разрядов кодовой комбинации k – количество информационных разрядов 2. Образующий полином: Р(х) = x10 + x9 + x7 + x1 + 1 3. Комбинация простого кода: G(х) = 24 4. Вероятность ошибки в канале: Pо = 5*10-5 5. Коэффициент группирования ошибок: a = 0.3 6. Способ представления циклического кодирования: представление циклического кода проверочными соотношениями . 2. ХАРАКТЕРИСТИКА СИСТЕМЫ РОС-НП. Структурная схема системы РОС-НПбл представлена далее. Работа системы происходит следующи м образом. При отсутствии сигнала переспроса к ИС от УУ идет сигнал готовности аппаратуры к передаче (ЗОК) и ИС соответственно выдает информационные комбинации (Л 1). Они поступают в кодер II одновременно запоминаются в н акопите ле Нпер емкостью h комбинаций (при отсутствии сигнала переспроса инфо рмац ии в Нпер з аменяется, сдвигаясь каж дый раз на одну комбинацию) . На приеме информационная часть очередной комбинации будет записана в Нпр и одновременно декодер так же, как и в системе с РОС-ОЖ, определит наличие или отсутствие ошибок в этой комбинации. Решающее устройство выдает соответствующий сигнал в УУ приемника ПК. Если ошибка не обнаружена, то УУ ст. Б формирует команду подтверждения, которая передается по обратному каналу и одновременно дает сигнал на вывод информационной комбинации из Нпр потребителю. Получая сигнал подтверждения, передатчик ст. А продолжает непрерывную передачу информации. Если же ошибка обнаружена, то УУ ст. Б формирует команду переспроса, передаваемую по обратному каналу на передатчик прямого канала ст. А. При реализации такой системы возникают трудности, вызванные конечным временем передачи и распространения сигналов. Если в некоторый момент закончен прием комбинации, в которой обнаружена ошибка, то к этому моменту по прямому каналу уже ведется передача следующей комбинации. Если время распространения сигнала в канале превышает длительность комбинации, то к моменту окончания приема комбинации с ошибкой может закончиться передача одной или нескольких комбинаций, следующих за ней. Еще некоторое число комбинаций будет передано до того времени, пока будет принят и проанализирован сигнал переспроса по второй комбинации. Так как передатчик повторяет лишь комбинации, по которым принят сигнал переспроса, то в результате повторения с запаздыванием порядок следования комбинаций, выдаваемых системой ПС, будет отличаться от порядка поступления комбинаций в систему. Но получателю комбинации должны поступать в том же порядке, в котором они передавались. Поэтому для восстановления порядка следования комбинаций в приемнике должны быть специальное устройство и буферный накопитель значительной емкости, поскольку возможны многократные повторения. Во избежание усложнения и удорожания приемников, системы с РОС - НП строят в основном таким образом, что после обнаружения ошибки приемник стирает комбинацию с ошибкой и блокируется на Н комбинаций (т. е. не принимает Н последующих комбинаций), а передатчик по сигналу переспроса повторяет h комбинаций (комбинацию с ошибкой и h — 1 комбинаций, следующих за ней). Такие системы с РОС-НП получили название систем с блокировкой РОС- НПбл . Эти системы позволяют организовать непрерывную передачу кодовых комбинаций с сохранением порядк а их следования. Поэтому одновременно с формированием сигнала переспроса УУ ст. Б блокирует (т. е. запрещает) вывод информации потребителю из Н пр на время, равное h комбинациям. Получив сигнал переспроса по обратному каналу, УУ ст. А ожидает конца передачи последней комбинации, во время которой получен этот сигнал. Затем ИС блокируется также на время передачи h комбинаций, а из Нпер в это время в канал через кодер передаются хранящиеся в накопителе последние h комбинаций. После их передачи ИС опять получает разрешение на передачу очередных комбинаций. Таким образом, последовательность передаваемых и принимаемых комбинаций не нарушается. 3. ОБЩАЯ ХАРАКТЕРИСТИКА КОДОВ, ПРИМЕНЯЕМЫХ В ПДС. 3.1. Принцип построения корректирующих кодов. Корректирующим кодом называется код, позволяющий обнаруживать или обнаруживать и исправлять ошибки в дискретных сообщениях, возникающие в каналах с помехами. Корректирующие коды могут использоваться в системах с обратной и без обратной связи. В системах с обратной связью корректирующие коды используются в режиме обнаружения ошибок, а в системах без обратной связи – в режиме исправления ошибок. Иногда в системах без обратной связи допускается режим обнаружения ошибок. При обнаружении ошибок в кодовой комбинации она не выдается получателю, т.е. считается, что лучше получателю выдать сигнал стирания, нежели неправильный символ. Идея построения корректирующих кодов заключается в том, что для передачи сообщения используется не все множество возможных кодовых комбинаций, а лишь некоторая их часть (разрешенные комбинации), отличающиеся друг от друга более чем в одном разряде. Все остальные комбинации для передачи не используются и относятся к числу запрещенных кодовых комбинаций. При использовании корректирующих кодов ошибка в одном разряде приводит к замене разрешенной кодовой комбинации неразрешенной, что позволяет обнаружить ошибку. При достаточно большом отличии разрешенных комбинаций друг от друга возможно обнаружение двух-, трехкратной и т.д. ошибки, поскольку они будут приводить к образованию неразрешенных комбинаций. Если под воздействием помех переданная комбинация трансформировалась в разрешенную, то она не будет обнаружена. При обнаружении ошибки недостаточно только выявить наличие ошибки в принятой комбинации, но необходимо также определить их место нахождения. Общее число всевозможных комбинаций кода длины n равно: Nn =2n . Число разрешенных кодовых комбинаций определяется числом информационных разрядов и равно: Nk =2k =2n - r , где r - число проверочных разрядов. Таким образом, число разрешенных кодовых комбинаций в 2r раз меньше общего числа комбинаций. 3.2. Классификация и характеристики корректирующих кодов. Корректирующие коды делятся на два класса - блочные и непрерывные. К блочным относятся коды, в которых каждому символу алфавита сообщений соответствует блок (кодовая комбинация) из n(i) элементов, где i – номер сообщения. Если n(i)=n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Если длина блока зависит от номера сообщения, то блочный код называется неравномерным. При использовании блочных кодов передаваемая информационная последовательность разбивается на отдельные блоки, которые кодируются и декодируются независимо друг от друга. Непрерывные коды представляют собой непрерывную последовательность разрядов, и разделение ее на отдельные блоки невозможно. В таких кодах проверочные элементы помещаются в определенном порядке между информационными. Блочные коды, в свою очередь, делятся на разделимые и неразделимые. Разделимыми называются коды, в которых элементы разделяются на информационные и проверочне. Последние и вносят в код избыточность, необходимую для обнаружения или исправления ошибок. В разделимых кодах информационные и проверочные разряды занимают всегда одни и те же позиции в кодовой комбинации. Разделимые коды обозначаются как (n, k) - коды, где n - длина или число разрядов кода; k - число информационных разрядов. Неразделимые коды свойством разделимости не обладают. Среди разделимых кодов различают коды систематические и несистематические. Систематическими называются такие блочные разделимые коды, в которых проверочные разряды представляют собой линейные комбинации информационных. Основными характеристиками корректирующих кодов являются: Вес кодовой комбинации (W) - число единиц в кодовой комбинации. Минимальное кодовое расстояние (dmin). Число разрядов, которыми различаются две кодовые комбинации, называется кодовым расстоянием между двумя комбинациями. Наименьшее из кодовых расстояний в коде называется минимальным кодовым расстоянием. Степень различия комбинаций характеризуется расстоянием Хемминга. Расстояние Хемминга для любых двух кодовых комбинаций определяется числом несовпадающих в них разрядов. 3.3. Циклические коды. Циклические коды обеспечивают обнаружение и исправление, как независимых ошибок (одиночных и многократных), так и пачек ошибок. Циклические коды обладают двумя важными свойствами. Во-первых, сумма по модулю два любых двух разрешенных комбинаций циклического кода также является разрешенной кодовой комбинацией. Отсюда следует, что наименьшее кодовое расстояние в циклическом коде определяется наименьшим весом его комбинаций. Во-вторых, если в разрешенной кодовой комбинации осуществить циклическую перестановку элементов этой комбинации, то в результате получится другая разрешенная кодовая комбинация, принадлежащая данному коду. Циклические коды относятся к блочным систематическим кодам. Код Хэмминга, исправляющий одиночные ошибки, представляет собой частный случай циклического кода. Введем следующие обозначения: G(x) - многочлен, отображающий комбинацию информационных элементов (степень многочлена - k-1); R(x) - многочлен, отображающий комбинацию из r проверочных элементов; F(x) - многочлен, отображающий кодовую комбинацию в целом (степень многочлена - n-1=k+r-1); F(x) = xr G(x) + R(x). Комбинация циклического кода F(x) образуется из исходной комбинации информационных разрядов G(x) путем умножения на полином P(x). Поэтому полином Р называется образующим. Разрешенные кодовые комбинации циклического кода характеризуются тем, что все они делятся без остатка на образующий полином P(x). Это условие выполняется, если R(x) равен остатку от деления xr G(x) на Р(x). Обнаруживающие ошибки свойства циклического кода основаны на том, что разрешенные комбинации кода F(x) делятся на образующий полином P(x) без остатка, а запрещенные - с остатком. Комбинации циклического кода формируются следующим образом: многочлен G(x), отображающий информационную k-разрядную кодовую комбинацию, умножается на xr , т.е. производим сдвиг k-разрядной кодовой комбинации на r разрядов. произведение xr G(x) делится на образующий полином P(x), и полученный остаток R(x) определяет r проверочных разрядов кодовой комбинации; кодовая комбинация F(x)=R(x)+xr G(x) является разрешенной, так как она делится без остатка на P(x). 4. АНАЛИЗ ВОЗМОЖНОСТЕЙ ЗАДАННОГО ЦИКЛИЧЕСКОГО КОДА. 4.1. Составление порождающей матрицы и матрицы проверок. Образующий полином : p ( x ) = x 10 + x 9 + x 7 + x 1 +1 Составим образующую матрицу в неканоническом виде G(15,5) : x4 * P(x) x14 +x13 +x11 +x5 +x4 11010 0000110000 x3 * P(x) x13 +x12 +x10 +x4 +x3 01101 0000011000 G(15,5) = x2 * P(x) = x12 +x11 +x9 +x3 +x2 = 00110 1000001100 x1 * P(x) x11 +x10 +x8 +x2 +x1 00011 0100000110 x0 * P(x) x10 +x9 +x7 +x1 +1 00001 1010000011 Далее составим образующую матрицу в каноническом виде G(15,5) : Номера строк, которые необходимо сложить по модулю 2 G(15,5) = |E(5,5) R(5,10)| 1+2+3+5 10000 0010100111 2+3+4 01000 1100010010 3+4+5 00100 0110001001 4+5 00010 1110000101 Переписываем 00001 1010000011 Матрица проверок H(15,5) : 01011 1000000000 01110 0100000000 10111 0010000000 00000 0001000000 H(15,5) = |RT (10,5) E(10,10)| = 10000 0000100000 01000 0000010000 00100 0000001000 10010 0000000100 11001 0000000010 10111 0000000001 4.2 Определение минимального кодового расстояния. Минимальное кодовое расстояние равняется минимальному количеству столбцов матрицы H(15,5) , при сложении которых по модулю 2, получается столбец, состоящий из всех нулей. Для определения минимального кодового расстояния dmin воспользуемся матрицей проверок H(15,5) : 01011 1 00 0000000 01110 0 10 0000000 10111 0 01 0000000 00000 0 00 1000000 H(15,5) = |RT (10,5) E(10,10)| = 10000 0 00 0100000 01000 0 00 0010000 00100 0 00 0001000 10010 0 00 0000100 11001 0 00 0000010 10111 0 00 0000001 Для данной матрицы проверок при сложении столбцов (выделенных на матрице жирным шрифтом) по модулю 2, мы получим столбец, состоящий из всех нулей. Таким образом, для данного образующего полинома: Р(х) = x10 +x9 +x7 +x1 +1 , минимальное кодовое расстояние равно 5 . 4.3. Составление таблицы всех ненулевых разрешенных кодовых комбинаций и определение их веса. Число вариан-тов № №№ строк G (15,5) Информационные элементы Проверочные элементы Вес w 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 6 2 2 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 5 C5 1 = 5 3 3 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 5 4 4 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 6 5 5 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 5 6 1+2 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 9 7 1+3 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 7 8 1+4 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 6 9 1+5 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 5 C5 2 = 10 10 2+3 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 8 11 2+4 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 7 12 2+5 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 6 13 3+4 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 5 14 3+5 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 6 15 4+5 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 5 16 1+2+3 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 8 17 1+2+4 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 5 18 1+2+5 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 8 19 1+3+4 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 9 C5 3 = 10 20 1+3+5 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 10 21 1+4+5 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 7 22 2+3+4 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 8 23 2+3+5 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 5 24 2+4+5 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 6 25 3+4+5 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 8 26 1+2+3+4 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 10 27 1+2+3+5 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 11 C5 4 = 5 28 1+2+4+5 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 10 29 1+3+4+5 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 6 30 2+3+4+5 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 11 C5 5 = 1 31 1+2+3+4+5 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 11 4.4. Определение доли необнаруженных ошибок. Кратность ошибок Число вариантов Cn i Число bi Доля необнаруженных ошибок bi / Cn i 1/2n-k 1 C15 1 = 15 - 0 9,76*10-4 2 C15 2 = 105 - 0 9,76*10-4 3 C15 3 = 455 - 0 9,76*10-4 4 C15 4 = 1365 - 0 9,76*10-4 5 C15 5 = 3003 8 2,66*10-3 9,76*10-4 6 C15 6 = 5005 7 1,39*10-3 9,76*10-4 7 C15 7 = 6435 3 4,66*10-4 9,76*10-4