Министерство  Образования РБ 

Белорусский Государственный  Университет Информатики  и Радиоэлектроники

ВМСИС

Курсовой  проект по курсу «Схемотехника»

На тему: «Преобразователь двоичного кода в код Хемминга с исправлением одиночных и обнаружением двойных ошибок». 
 
 
 
 
 
 
 
 
 
 

Минск 2011

Белорусский Государственный  Университет Информатики  и Радиоэлектроники

наименование  высшего учебного заведения 
 
 
 

Задание

по курсовому  проектированию

студенту  гр.700502 Тетереву А. В.

1. Тема проекта: Преобразователь двоичного кода в код Хэмминга с обнаружением и исправлением одиночных и обнаружением двойных ошибок.
2. Строка сдачи студентом законченного проекта_________________________________________
3. Исходные данные к проекту:
1. Количество информационных разрядов 14
2. Критерий оптимизации P_min.
3. Тип логики: Рг_вх – КМОП; КУ – ТТЛ; КрУ – ЭСЛ; Рг_вых – ЭСЛ.
4. Содержание расчётно-пояснительной записки

   Введение.

   1. Обзор литературы.

   2. Составление структурной схемы.

   3. Разработка функциональной  схемы. 

   4. Выбор элементов  и разработка принципиальной схемы 

Задание принял к исполнению

“26”   июня   2010г. (_______) (Тетерев А.В.)

Руководитель  КП 

“__”__________2003г. 
Введение.

      Основные  методы повышения надежности цифровых устройств – применение более надежных деталей, их предварительная тренировка, оптимальное (в смысле надежности) построение схем и выбор режимов их работы, усовершенствование технологии изготовления и конструкции элементов и устройств, применение интегральной технологии – не позволяют решить задачу получения требуемой надежности из-за сложности и ответственности современных систем. Поэтому в настоящее время разрабатываются и практически используются различные методы введения избыточности (резервирование, мажоритарный принцип, избыточное кодирование информации и т. п.), позволяющие синтезировать устройства, в которых с высокой вероятностью автоматические обнаруживаются возникающие ошибки. Исправление ошибок производится также автоматически аппаратными и программными средствами или включением резервной аппаратуры.

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

      Так, в подавляющем большинстве современных  ЭВМ общего и специального назначения применяется код с нечетным количеством  единиц для контроля хранения и передачи информации. Для контроля работы арифметических устройств и адресных трактов оперативных запоминающих устройств в ряде случаев применяются простейшие арифметические коды, порождаемые одним модулем. Для обнаружения двойной ошибки и исправления одиночной в ОЗУ машины Sretch применялся код Хэмминга длиной 72 разряда, из которых 8 являются контрольными. Для тех же целей в отечественной управляющей машине общепромышленного назначения типа ВНИИЭМ-3 использовался код длиной 30 разрядов, из которых 24 являются информационными.

      В основном ЗУ машин фирмы IBM (модели 370\155 и 370\165) имелись аппаратные средства для исправления всех одиночных ошибок, обнаружения всех двойных и большинства многократных.

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

      Обеспечение требуемой достоверности при  передаче цифровой информации по каналам  связи невозможно без применения избыточного кодирования.

ОБЗОР ЛИТЕРАТУРЫ.

        Многообразие существующих методов борьбы с ошибками можно разделить на два класса: 1) синтез избыточных устройств, нечувствительных к определенному количеству неисправностей; 2) синтез системы обнаружения ошибок (системы контроля) (рис. 1.).

                        рис. 1. Классификация  способов борьбы с ошибками.

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

      Реализация  существующих методов борьбы с ошибками, как правило, приводит к уменьшению быстродействия системы. Поэтому в  каждом конкретном случае возникает  необходимость оценки степени уменьшения быстродействия или производительности избыточной системы по сравнению с неизбыточным вариантом.

      Введение  аппаратурной избыточности неизбежно  приводит к увеличению количества аппаратуры в системе.

      Рассмотрим  кратко основные методы синтеза схем, нечувствительных к определенному  количеству внутрисхемных неисправностей.

      Применение  восстанавливающих  элементов. Метод основан на разбиении устройства на ряд блоков (подсистем), увеличении их количества в соответствии с соотношением 2а+1 (где а – количество ошибок, которые должны быть исправлены) и включении на выходе каждой группы идентичных блоков специальных элементов, предотвращающих распространение ошибок на входы других блоков, если количество ошибок не превышает значения а. Наибольший практический интерес представляют мажоритарные элементы, у которых значение сигнала на выходе совпадает со значение сигнала на большинстве входов. На рис. 2. показан простейший пример использования мажоритарных элементов &M в схеме полусумматора (ПС). Этот метод позволяет синтезировать схемы с высоким уровнем надежности, но требует увеличения количества аппаратуры как минимум в 4 -  5 раз. Быстродействие снижается незначительно.

      Логика  с переплетениями. Особенностью логики с переплетениями, исключающей необходимость использования отдельных восстанавливающих элементов, является совмещение операций по обработке сигналов в логическом элементе с исправлением ошибок за счет введения избыточных переменных. Характерным представителем систем этого класса является учетверенная логика. Рассматриваемый метод введения избыточности используется в устройствах, реализуемых с помощью логических элементов И – НЕ, ИЛИ – НЕ или И – ИЛИ – НЕ. Для получения независимых версий одного сигнала все логические элементы исходной (неизбыточной) схемы учетверяются. Совокупность из четырех элементов, соответствующих одному элементу в неизбыточной схеме, называют слоем. Исправление ошибок, возникающих из-за неисправностей в логических элементах, происходим благодаря специальной организации связей между элементами слоев. Предполагается, что неисправности элементов порождают ошибки двух типов: «ложная единица» и «ложный нуль».

      Например, пусть некоторая логическая переменная представлена двумя сигналами: х1 и  х2, поступающими на элемент И –  НЕ. Данный элемент реализует функцию  ; если один из сигналов содержит ошибку «ложная единица», то она не пройдет на выход данного логического элемента. Если же один из сигналов

                  рис. 2. Введение избыточности с помощью мажоритарных элементов.

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

      С помощью данного метода введения избыточности можно синтезировать  схемы с высокой надежностью  без применения восстанавливающих  элементов. Однако нагрузка по входу  и выходу на логические элементы значительно  увеличивается. Количество аппаратуры увеличивается в 4 раза. Но вот быстродействие схемы практически не изменяется.

      Постоянное  резервирование комплектующих деталей в логических элементах применяется в тех случаях, когда наблюдается существенная асимметрия в характере неисправностей деталей. Например, если в диоде или транзисторе неисправность типа «обрыв» случается много чаще, чем «короткое замыкание», то данный элемент можно резервировать с помощью параллельного включения второго диода (транзистора). Если короткое замыкание возникает чаще, чем обрыв, то применяется последовательное включение резерва.

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

рис.3. введение избыточности по методу избыточного кодирования.

исходная  схема содержит k выходов, называемых информационными. Дополнительная схема, содержащая r выходов, синтезируется таким образом, чтобы при любом наборе входных сигналов совокупность из n=k+r сигналов на выходах основой и дополнительной схем соответствовала некоторому корректирующему коду, который позволяет исправить наиболее вероятные ошибки. Ошибки,  возникающие в основной и дополнительной схемах из-за неисправностей их элементов, исправляются корректирующим устройством (КУ). Важной характеристикой корректирующего кода является отношение количества информационных разрядов k к общей длине кода n/ в случае кодов Хэмминга, позволяющих исправить любую одиночную ошибку, эти параметры связаны соотношением k=2^r-1-r, где r – количество контрольных разрядов. Например, если r=4, то k=11,n=k+r=15.

      Однако  избыточность кода (значение отношения  k/n) – не единственный и даже не главный показатель, определяющий количество аппаратуры в избыточном устройстве, так как необходимо учитывать затраты аппаратуры на реализацию КУ. Поэтому во многих случаях вместо кода с минимальной избыточностью выбирают код с большей избыточностью, но позволяющий более просто выполнить декодирование информации. Суммарные затраты аппаратуры сильно зависят от особенностей конкретной схемы и при введении избыточности данным методом могут увеличиваться в 2 и более раз по сравнению с неизбыточным вариантом.

      Наличие КУ несколько уменьшает быстродействие избыточной схемы по сравнению с  неизбыточной.

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

      Рассмотрим  код Р. Хэмминга.

      Коды  Хемминга с минимальным расстоянием  d_min =3 наиболее просто описываются с помощью контрольной матрицы, вектор-столбцы которой различны и отсутствует нулевой столбец, соответствует коду с минимальным расстоянием d_min =3.

      Для определенности выберем в качестве вектор-столбцов матрицы различные  четырехразрядные двоичные числа (исключая число нуль):

      Перестановкой столбцов, содержащих одну единицу, показанную матрицу можно привести к виду

      Данная  матрица соответствует коду Хэмминга с минимальным расстоянием d_min =3. Использование такого кода позволяет исправить любую одиночную ошибку. Если нумерацию информационных и контрольных разрядов разделимого кода производить слева направо, то в соответствии с матрицей получаем систем линейных уравнений, с помощью которых вычисляются контрольные разряды

      где -контрольные разряды, -информационные разряды.

      Если  при передаче кодового слова возникнет  одиночна ошибка, то окажутся невыполненными те контрольные соотношения (уравнения для ), в которые входит значение ошибочного разряда. Например, если ошибка возникла в первом информационном разряде, то окажутся невыполненными третье и четвертое уравнения, то есть корректор будет равен 0011, совпадая с первым вектор столбцом матрицы. Отсюда получаем алгоритм определения места одиночной ошибки. Ясно, что вычисленное значение корректора обязательно совпадает с одним из вектор-столбцов матрицы, так как в качестве вектор-столбцов было выбраны все возможные двоичные 4-разрядные числа.

      Если  возникнет ошибка кратности 2, то полученное значение корректора также будет  совпадать с одним из вектор-столбцов и ошибки автоматически исправляются. Однако замети, что после такого «исправления» получается кодовое слово, не совпадающее с требуемым кодовым словом. Значение корректора, соответствующее ошибке кратности 2 и более, получается при помощи поразрядного суммирования по модулю 2 вектор-стобцов матрицы, соответствующих ошибочным разрядам.

      Другими словами, если при передаче кодового слова

      возникнет ошибка в  _{и то при автоматическом исправлении будет получено слово} , которое хотя и не совпадает с переданным, но является кодовым. Поэтому, когда вероятность возникновения ошибок кратности более единицы значительно, автоматическое исправление ошибок оказывается нежелательным. В этом случае необходимо предусматривать только обнаружение ошибки.

      В случае, если нужно одновременно и исправлять одиночные, и обнаруживать двойные ошибки, можно еще больше увеличить избыточность корректирующего кода так, чтобы его d_min =4. В принципе такой код можно построить, несколько модифицировав обычный код Хемминга. Для этого необходимо иметь еще один, дополнительный, контрольный разряд. Этот разряд, в частности, можно использовать для проверки на четность (или нечетность) всего информационного слова. Поскольку код с проверкой на четность не реагирует на ошибки четной кратности (двойные, четверные и т. д.), но зато выявляет все ошибки нечетной кратности (одиночные, тройные и т. д.), то он в известном смысле хорошо дополняет (модифицирует) код Хемминга.

Разработка  структурной схемы.

      Данное  устройство строится, основываясь на рассмотренной выше схеме (рис.3).

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

      Исходя  из вышесказанного, очевидно, что преобразователь двоичного кода в код Хэмминга должен содержать следующие блоки:

      Входной регистр (Рг.вх.) – для приема, хранения и выдачи данных.

      Кодирующее  устройство (КУ) – для формирования контрольных разрядов. Представляет собой свертку информационных разрядов по модулю 2. Результат свертки – получение контрольных разрядов.

      Корректирующее  устройство (КрУ) – для обнаружения  и исправления ошибок (если они  есть)

      Выходной регистр (Рг.вых.) – для приема, и дальнейшей передачи данных.

      Между кодирующим и корректирующим устройствами подразумевается наличие канала связи.

Приложение.

            Структурная схема  преобразователя двоичного кода в код Хэмминга.

Разработка  функциональной схемы.

Формирование  контрольных разрядов.

      Доля  контрольных разрядов в общей  длине слова тем меньше, чем больше длина слова. Чтобы обеспечить защиту комбинаций в 8 разрядах, необходимо 5 контрольных разрядов. Следовательно, общая длина слова составит 13 разрядов. По методу Хэмминга каждый контрольный разряд слова соответствует различным информационным разрядам.

      Соответствие  контрольных разрядов информационным разрядам слова приведено в таблице:

*необходимость  этого столбца объяснена ниже. 

Формирование  кода ошибки.

      Разряды принятого кодового слова поступают на схему свертки по четности, здесь на каждой свертке обрабатывается вся группа вместе с ее контрольным разрядом. Выходы свертки образуют 4-разрядный код ошибки (корректирующий код – в таблице приведенной выше видна зависимость, по которой корректирующий код соответствует номеру информационного разряда). Если при передаче кодового слова произошла ошибка в одном из его разрядов, то будет зафиксировано нарушение четности именно в тех контрольных группах, в состав которых входит неверный разряд. В результате корректирующий код укажет номер неисправного разряда принятого кодового слова. Для восстановления первоначального слова неверный разряд нужно проинвертировать. Корректирующий код поступает на дешифратор, активный выход которого возбуждает управляемый инвертор (двухвходовый сумматор по модулю 2) в том разряде, где произошла ошибка.

      Для анализа ситуации при корректировке  введем понятия корректора К=К1+К2+К3+К4 (где Ki – выход i-ой свертки по четности) и контроль по четности Ч (сумма по модулю 2 всех разрядов числа). Тогда возникающие ситуации можно разделить на такие группы: 

      Для организации работы корректирующего  устройства введем следующие функции (сигналы):

      Сигнал  ошибки – сигнализировать о неисправимой ошибке:

О=КÅЧ

      В нашем случае, так как тройные или более высокой кратности ошибки – события практически невероятное, сигнал ошибки будет сообщать о двойной ошибке в блоке данных. Так же он будет служить запрещением записи слова в выходной регистр.

Сигнал коррекции  – при обнаружении исправимой ошибки будет включать дешифратор для ее исправления:

С=К&Ч

      Разработка  принципиальной схемы.

      ВХОДНОЙ РЕГИСТР.

      Входной регистр по условию курсового  проекта должен быть выполнен на цифровых микросхемах ТТЛ – логики.

      В соответствии с критерием оптимизации (f_max) наиболее подходящей следует признать микросхему К531ИР19П.

      Микросхема  К531ИР19П представляет собой четырехразрядный параллельный регистр.

      Условное  графическое обозначение (УГО) приведено  на рисунке:

      16-питание; 8- общий

  Назначение входов  и выходов:

            4,5,12,13 - информационные входы;

            1,9 - входы синхронизации;

            2,7,10,15- прямые выходы;

            3,6,11.14 - инверсные выходы.

      Основные  параметры К531ИР19П

      Для реализации восьмиразрядного регистра нам понадобится две микросхемы К531ИР19П.