metod_15.03.04_atppp_oaip_ump_2016 (Методические документы), страница 13

Наличие помех в канале связи приводит не только к искажениюпередаваемого сообщения и частичной утраты связанной с ним информации, но и куменьшению пропускной способности канала связи.Обеспечение надежности передачи данныхК. Шеннон доказал теоретическую возможность передачи сообщения без потерьинформации по реальным каналам, если при этом выполнен ряд условий.При передаче информации по каналу с шумом всегда имеется способ кодирования,при котором сообщение будет передаваться со сколь угодно высокой достоверностью,если скорость передачи не превышает пропускной способности канала.Помехоустойчивость достигается за счет повышения избыточности кода (т.е.увеличения длины кодовой цепочки); безусловно, возрастает время передачи, чтоследует считать платой за надежность.При помехоустойчивом кодировании сообщения для канала связи могут ставитьсядве задачи:• кодирование обеспечивает только установление факта искажения информации - вэтом случае исправление производится путем ее повторной передачи;• кодирование позволяет локализовать и автоматически исправить ошибкупередачи.Общим условием является использование только равномерных кодов.Надежность передачи при кодировании помехоустойчивым кодом обеспечиваетсятем, что вместе с разрядами сообщения Кс передается Кк контрольных разрядов.Избыточность сообщения для реального канала L характеризуется относительнойвеличиной:57L = (Кс + Кк)/Кс = 1 + (Кк/Кс).Относительная избыточность сообщения - это характеристика, показывающая,во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную(безошибочную) передачу (хранение).1.

Коды, обнаруживающие ошибкуПусть имеется цепочка информационных бит длиной Кс. Добавим к ним одинконтрольный бит Кк, значение которого определяется тем, что новая кодовая цепочкаиз (Кс + 1) бит должна содержать четное количество единиц - по этой причине такойконтрольный бит называется битом четности. Например, для информационного байта01010100 бит четности будет иметь значение 1, а для байта 11011011 бит четностиравен 0.Избыточность сообщения L = 1 + (1/Кс)2. Коды, исправляющие одиночную ошибкуМинимальная избыточность кода, исправляющего одиночную ошибку определяется: 1)Н = -p*log2p - (1 - p) *log2(1 - р) – неопределенность передачи одного бита сообщения;где р - вероятность появления ошибки в сообщении.

Для восстановленияинформационного содержания сообщения, очевидно, следует дополнительно передатьколичество информации не менее величины ее потерь, т.е. вместо передачи каждого 1бит информации следует передавать (1 + Н) бит. В этом случае избыточностьсообщения составитLmin =(1 +H)/1 = 1 – p* log2p - (1 - p) *log2(1 - р)В 1948 г. Р. Хемминг предложил код, устраняющий одиночные ошибки. Основнаяидея состоит в добавлении к информационным битам нескольких битов четности,каждый из которых контролирует определенные информационные биты. Еслипронумеровать все передаваемые биты, начиная с 1 слева направо (стоит напомнить,что информационные биты нумеруются с 0 и справа налево), то контрольными(проверочными) оказываются биты, номера которых равны степеням числа 2, а всеостальные являются информационными.

Например, для 8-битного информационногокода контрольными окажутся биты с номерами 1, 2, 4 и 8:10112010Номера кода Хеминга345601119876789101112011101543210Номера информационных битовКонтрольные разряды58Номера контролируемых битов для каждого проверочного приведены в таблице.Проверочныебиты12481632Контролируемые биты124816323359173356610183477711193591012122036111113132137131414142238151515152339171820242440191921252541….….….………В перечень контролируемых битов входит и тот, в котором располагаетсяпроверочный.

При этом состояние проверочного бита устанавливается таким образом,чтобы суммарное количество единиц в контролируемых им битах было бы четным.Легко усматривается принцип выделения контролируемых битов в таблице: длялюбого номера проверочного бита (n), начиная с него, п бит подряд оказываютсяпроверяемыми, затем - группа n непроверяемых бит; далее происходит чередованиегрупп.При построении кода начинают со старшего проверочного разряда кодасообщения. Пример. Закодировать по коду Хемминга сообщение 01101101.1 шаг – формируется значение 8-го старшего для данного кода значениеконтрольного разряда  0110 1101. Значение 8 разряда будет 1, т.к.

в исходном кодезначение 8 – 11 разрядов при сложении по модулю два дают 1.2 шаг – формирование 4-го контрольного разряда по исходному коду011011101. Онобудет равно 1. Код станет 0111011101.3 шаг – определение значение второго контрольного разряда. Оно будет равно 0.4 шаг – значение первого контрольного разряда равно 0. Значение передаваемогокода будет 000111011101.Пусть вместо указанной выше последовательности 000111011101 на приемномконце принята последовательность, у которой в пятом разряде вместо 1 принят 0.При проверке анализируются проверочные разряды, начиная с младшего:1 шаг – значение первого проверочного разряда 1 – не верно, что означает ошибку водном из нечетных разрядов;2 шаг – значение второго проверочного разряда 0 – верно, что означает отсутствиеошибки в 3, 7 и 11 разрядах кода (остаются 5 и 9разряды);3 шаг – значение четвертого проверочного разряда 1 - не верно, что означаетотсутствие ошибки в 9 разряде и наличие ошибки в 5 разряде.Номер бита, содержащего ошибку (5), равен сумме номеров контрольных битов,указавших на ее существование (1 и 4) - это не случайное совпадение, а общеесвойство кодов Хемминга.На основании сказанного можно сформулировать простой алгоритм проверки иисправления передаваемой последовательности бит в представлении Хемминга:(a) произвести проверку всех битов четности;(b) если все биты четности верны, то перейти к п.(е);59(c) вычислить сумму номеров всех неправильных битов четности;(d) инвертировать содержимое бита, номер которого равен сумме, найденной в п.(с);(e) исключить биты четности, передать правильный информационный код.Избыточность кодов Хемминга для различных длин передаваемыхпоследовательностей приведена ниже:Число информационныхбитов81632Число контрольныхИзбыточность,битовL4561,51,311,06Безусловно, данный способ кодирования требует увеличения объема памятикомпьютера приблизительно на одну треть при 16-битной длине машинного слова,однако, он позволяет автоматически исправлять одиночные ошибки.

Поэтому,оценивая время наработки на отказ, следует исходить из вероятности появления парной ошибки в одной последовательности (т.е. сбои должны произойти в двух битаходновременно). Расчеты показывают, что для указанного ранее количества ячеек впамяти объемом 1 Мбайт среднее время появления ошибки составляет более 80 лет,что, безусловно, можно считать вполне приемлемым с практической точки зрения.Способы передачи данных в компьютерахВ компьютерных линиях связи используются два способа передачи:• параллельный, когда передаются одновременно все биты машинного слова;• последовательный, когда биты передаются поочередно, начиная с младшего.1. Канал параллельной передачиДля одновременной передачи нескольких сигналов, очевидно, требуется линиясвязи, количество проводников в которой совпадает с числом передаваемых сигналов.Такая линия связи называется шиной.

Количество проводников определяет ширину илиразрядность шины. Например, во внутренних линиях компьютера могутиспользоваться 16-ти и 32-х разрядные шины. На рис. 5.2. показана линияпараллельной передачи, связывающая регистр АЛУ и ячейку памяти компьютера.Шина обеспечивает наиболее быстрый способ передачи информации.Параллельный способ передачи используется во внутренних линиях связикомпьютера, а также для связи с внешними устройствами, подключаемыми кпараллельному порту компьютера.Недостатки параллельного способа передачи: невозможность передачи на большие расстояния (более нескольких метров),поскольку из-за электроемкости между проводниками в них возникают наводки. данный способ требует многожильных специальных проводов для связи, чтосущественно повышает стоимость линии.2. Последовательная передача данных60Для передачи информации на большие расстояния используется последовательныйспособ передачи.