Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 38)

КОДЫ ХЕММИНГА

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

В основе метода лежит принцип проверки некоторого подмножества бит на четность, то есть рассматривается число двоичных единиц в рассматриваемом подмножестве, которое (число) должно быть четным (или, если по-другому договориться, нечетным; принципиально здесь разницы нет, но дополнение до нечета несколько лучше электротехнически, так как здесь обнаруживается разница между нулем и отсутствием сигнала). Любое контролируемое подмножество бит при этом должно содержать контрольные разряды.

Проверки должны быть построены так, чтобы в совокупности давать максимум информации о наличии и положении ошибки. Для этого они должны быть независимы. Это означает, что никакая сумма одних проверок не совпадает ни с какой другой проверкой. Например, три проверки на четность в позициях

1: 1,2, 5, 7

2: 5, 7,8,9

3: 1,2, 8,9

являются зависимыми, поскольку сумма любых двух строк покрывает третью строку.

Пусть нам дано m контрольных разрядов. С их помощью можно различить не более 2^m событий. Одно из них состоит в том, что все символы сообщения правильны, а остальные должны давать местоположение одной из n возможных одиночных ошибок. Это приводит к неравенству

или

Если имеет место точное равенство, то код называется совершенным. В совершенном коде Хемминга имеется 2^m-1 разрядов, из которых 2^m-m-1 информационных.

Существует понятие избыточности кода, определяемое как отношение общего числа бит в сообщении к числу полезных бит. Для кода Хемминга избыточность быстро уменьшается с ростом размера информационного блока, и в пределе равна 1+log₂n.

Контрольные разряды сообщения ставятся в позиции, соответствующие целым неотрицательным степеням числа 2, то есть в позиции 1,2, 4,8,16,… и т.д. Для того, чтобы определить номера разрядов, входящих в соответствующую проверку, выпишем двоичное представление номеров позиций:

В первую проверку включим те разряды, двоичные номера которых содержат единицу в младшем разряде, во вторую – те, у которых 1 стоит во 2-м справа разряде номера и т.д. Получатся следующие последовательности проверок:

1: 1,3,5,7,9,11,13,15,…

2: 2,3,6,7,10,11,14,15,…

3: 4,5,6,7,12,13,14,15,…

4: 8,9,10,11,12,13,14,15,…

……………………………

Синдромом называется двоичное число, состояшее из m бит, которое получается, если написать символ 0 для каждой выполненной проверки, и 1 – для каждой невыполненной. Нулевой синдром означает отсутствие ошибки, в противном случае он будет указывать позицию ошибки. Поскольку информационные и проверочные символы принимают равное участие в кодовом слове, код является равномерно защищенным.

Для иллюстрации сказанного приведем следующий простой пример на 15-разрядной сетке. Через K_r обозначим контрольные разряды сообщения, а через I_s ­– информационные. Пусть требуется передать следующие 11 бит информации: 01101111010. Примем методику дополнения до нечета. Сначала заполним информационные позиции, а затем построим соответствующие контрольные:

Пусть при передаче сообщения ошибка появилась в одном из разрядов, например, в 10-м. Внесем в разрядную сетку «испорченное» сообщение и найдем синдром S.

Разряды первой проверки дают нечетное (3) число единиц, значит, она выполняется и мы пишем 0. Вторая проверка дает 6 единиц, значит, она не выполнена, и мы пишем 1. Аналогично выполнив оставшиеся проверки, получим синдром S=1010, что соответствует числу 10. Следовательно, в принятом сообщении следует исправить 10-й разряд.

Что произойдет в случае двойной ошибки ? Система вычислит ненулевой синдром, но теперь он уже не будет правильно указывать позицию ошибки. Следовательно, вместо двух ошибок мы будем иметь три. Для получения кода с дополнительным обнаружением двойных ошибок (без возможности исправления) добавим ещё одну проверку на четность и еще один разряд, охватив проверкой всё сообщение. Тогда каждая одиночная ошибка по-прежнему будет давать правильный синдром, а дополнительная проверка – 1. Обзор возможных случаев приводится в следующей таблице:

Ошибки более высокой кратности достаточно редки, и необходимость их корректировки может возникнуть при создании систем повышенной надежности, например, в авиационной, военной или космической технике. Вероятность появления k – кратной ошибки в блоке из n бит при вероятности ошибки в отдельном бите, равном p, и независимом возникновении ошибок в разных разрядах, выражается формулой

и при малых p быстро уменьшается с ростом k.

Логические основы проектирования цифровых устройств. Понятие функционально- полного набора логических элементов. Полусумматор и сумматор.

Задачи, решаемые при разработке цифровых логических устройств, можно разделить на две категории:

1. Синтеза.

2. Анализа.

Синтез - это процесс построения схемы цифрового устройства по заданию.

Анализ - процесс обратный синтезу.

дискретного устройства, отражающая только его свойства по переработке сигналов, называется дискретным (цифровым) автоматом.

В общем случае, модель представляет собой многополюсный черный ящик с m входами и n выходами (рис.1.3). Состояние автомата определяется состояниями сигналов на его входах и выходах. Совокупность входных и выходных переменных Х и Z образуют входное и выходное слово автомата, соответственно.

Различные значения входных переменных образуют алфавит (т.к. алфавит входных и выходных переменных един, в дальнейшем будет рассматриваться только один алфавит). В цифровой технике алфавит входного (выходного) слова содержит два значения (две буквы) "1" и "0".

Каждое слово - набор переменных на входе или на выходе автомата, отличается от другого слова хотя бы одной буквой. Каждая буква слова поставлена в соответствие с номером входа (выхода) автомата.

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

1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)

2) "И-НЕ" (базис Шеффера)

3) "ИЛИ-НЕ" (базис Пирса или функция Вебба).

Элементы, реализующие операцию "И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных и структурных схемах изображаются так:

Полусумматор находит сумму двух двоичных чисел 0 и 1 согласно таблице сложения:

Пусть p и q обозначают числа, которые требуется сложить, d₀ – младший разряд суммы, d₁ – старший (разряд переноса). Тогда приходим к следующим таблицам истинности:

Характеристики

Список файлов ВКР