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

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

ВМСИС

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

 

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

Минск 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 и более раз по сравнению с неизбыточным вариантом.

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

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

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