Основные аксиомы, теоремы и тождества алгебры логики

КОМБИНАЦИОННЫЕ СХЕМЫ

 

Основные аксиомы, теоремы и тождества алгебры логики

Методы синтеза и анализа всех классов цифровых схем построены на базе алгебры логики, которая является основным математическим аппа­ратом описания и преобразования структуры цифровых схем [1].

В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и 1 (например, 0 – событие не происхо­дит, 1 – происходит; 0 – ложное высказывание, 1 – истинное; 0 – низкий уровень напряжения, 1 – высокий; 0 – разомкнутый контакт, 1 - замкну­тый). Значения переменных не отображают каких-либо количественных значений, а имеют лишь символическое значение.

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

Все тождества записаны парами на основании того, что по прин­ципу двойственности из одного тождества пары можно получить другое взаимной заменой операций дизъюнкции и конъюнкции, а также значений 0 и 1. Тождества (4.1) и (4.2) самодвойственны, так как они не изменяются по принципу двойственности.

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

Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции.

 

Упражнения

Доказать истинность следующих утверждений.

1. = ( ).

2. .

3. = ( )( ).

4. = ( ) .

5. ( )( )( ) = .

6. = a.

7. = .

8. = .

Убедиться в истинности тождеств, полезных для упрощения выражений, содержащих операцию .

9. а) , б) , в) , г) .

10. а) , б) , в) ,

г) , д) , е) .

11. а) , б) .

12. .

13. .

 

Переключательные функции

Любое логическое выражение, составленное из n переменных с по­мощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию n переменных. Двоичная функция может прини­мать только два значения: 0 и 1 – в зависимости от значений переменных. Такие функции являются удобным инструментом для описания, анализа и синтеза переключательных схем (бесконтактных и контактных), поэтому они называются переключательными функциями (ПФ).

Для ПФ n переменных x₀, …, x_n-1 будем использовать обозначение y (x₀, …, x_n-1). Совокупность значений переменных, в которой каждая пе­ременная может принимать значения 0 или 1, называется набором. Любая функция n переменных может быть определена на 2ⁿ наборах. Это следует из того, что каждому набору соответствует n-разрядное двоичное число, а количество различных двоичных чисел при n разрядах равно 2ⁿ.

Существуют несколько способов задания ПФ.

1. Табличный, когда функция задается в виде таблицы истинности (соответствия). Таблица истинности содержит 2ⁿ строк ( по числу набо­ров), n столбцов значений аргументов и один столбец значений функции. В таблице каждому набору аргументов соответствует значение функции.

Таблица истинности ПФ, значения которой соответствуют значени-

ям, принимаемым большинством переменных в наборе (функция голосования), определяет ПФ мажоритарного элемента “два из трех” (переноса двоичного разряда.

2. Координатный способ, когда функция задается в виде координатной карты состояний, например в виде карты Карно. Карта содержит 2ⁿ клеток по числу набо­ров значений переменных. Каждая клетка задается коор­динатами строки и столбца, соответствующими определенному набору. Все аргументы разбиваются на две группы так, что одна группа определяет координаты строки, а другая – столбца. Порядок записи значений переменных в каждой группе задается записью переменных в соответствующем порядке над столбцами и около строк. Кодовые комбинации, задающие координаты двух соседних столбцов (строк), соответствуют двум соседним кодовым комбинациям циклического кода Грея.Соседние

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

На рис. 1, а приведена карта Карно для ПФ мажоритарного элемента “два из трех”, заданной таблицей истинности 2, на рис.1, в – для ПФ компаратора. На рис.1, б, г в клетках проставлены их номера, соответству-

ющие номерам наборов.

Карты Карно являются важным средством проектирования логических схем. Особенность карт в том, что любые две соседние клетки отличаются значением какой-либо одной и только одной переменной. Эта особенность характеризует также клетки первой и последней строк, первого и последнего столбцов, поэтому такие клетки тоже можно считать соседними. Указанная особенность соседних клеток позволяет легко осуществлять упрощение ПФ посредством использования тождества склеивания.

3. Числовой способ, когда ПФ задается в виде десятичных номеров тех наборов переменных, на которых функция принимает значение 1. При этом следует учитывать, что i-я двоичная переменная имеет “вес” 2ⁱ. Например, приписывая переменным x₂, x₁, x₀ соответственно “веса” 2², 2¹, 2⁰, в числовом виде ПФ рис.1, а будет задана как y( x₂, x₁, x₀ ) = ( 3, 5, 6, 7 ).

Можно использовать для задания функции десятичные номера наборов, на которых функция принимает значение 0. Та же ПФ (рис.1, а) в таком случае будет задана как y( x₂, x₁, x₀ ) = ( 0, 1, 2, 4 ).

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

При использовании всех n аргументов для записи алгебраического выражения существует две формы структурных формул.

Совершенная дизъюнктивная нормальная форма (СДНФ) представляет собой дизъюнкцию минтермов.

Минтерм (минимальный терм, конституента единицы) есть логическое произведение всех переменных ПФ для наборов, на которых ПФ принимает значение 1.Если в наборе переменная равна 1, то в минтерм эта переменная входит без инверсии, если равна 0 - то с инверсией. Например, если на наборе x₂ = 0, x₁ = 1, x₀ =1 ПФ принимает значение 1, то соответствующий минтерм m₃ для третьего набора будет иметь вид m₃ = x₁ x₀.

Пример: СДНФ для ПФ мажоритарного элемента (рис.1, а)

y= m₃ m₅ m₆ m₇ (1)

Совершеннаяконъюнктивная нормальная форма (СКНФ) представляет собой конъюнкцию макстермов.

Макстерм (максимальный терм, конституента нуля) есть логическая сумма всех переменных ПФ для наборов, на которых ПФ принимает значение 0. Если в наборе переменная равна 1, то в макстерм эта переменная входит с инверсией, если равна 0 - то без инверсии. Например, если на наборе x₂ = 0, x₁ = 0, x₀ =1 ПФ принимает значение 0, то соответствующий макстерм M₁ для первого набора будет иметь вид .

Пример: СКНФ для ПФ мажоритарного элемента (рис.1, а)

y =M₀M₁M₂M₄ =( )( )( )( ).(2)

Минтермы (макстермы) называются соседними, если они отличаются формой представления только одной переменной (без инверсии, с инверсией). В примере (1) минтерм m₇ является соседним по отношению ко всем остальным (m₃, m₅, m₆). В примере (2) макстерм М₀ является соседним по отношению ко всем остальным (М₁, М₂, М₄).Признак соседства минтермов (макстермов) используется при применении закона склеивания (при минимизации ПФ с применением карт Карно).

Определение “совершенная форма” означает, что все минтермы или макстермы имеют одинаковую размерность (ранг), равную числу переменных n, от которых зависит ПФ.

Определение “нормальная форма” означает, что порядок логического уравнения не более двух. Порядок логического уравнения – количество последовательно выполняемых базовых операций алгебры логики при вычислении значения функции (операция инверсии в расчет не принимается). При реализации логических схем порядок ПФ определяет число каскадов логического преобразования входных переменных, необходимых для получения функции.

Можно привести и более простые алгебраические выражения для ПФ мажоритарного элемента (рис.1, а):

(3)

y = ( )( )( ) (4)

Способ их получения рассмотрен ниже.

 

Упражнения

Для заданной ПФ: а) составить таблицу истинности;

б) получить СДНФ; в) получить СКНФ; г) построить карту Карно.

 

14. y( x₂, x₁, x₀ ) = ( 0, 1, 2, 4 ).

15. y( x₃, x₂, x₁, x₀ ) = ( 1, 3, 5, 9, 11, 13 ).

16. y( x₃, x₂, x₁, x₀) = ( 0, 2, 7, 8, 10, 15 ) + ( 4, 5, 6, 12, 13, 14 ).

17. y( x₃, x₂, x₁, x₀ ) = x₃ x₁ x_{2 1} x_{0 3 2} x₁ x₀.

18. y( x₂, x₁, x₀ ) = m₀ m₁ m₂ m₄ m₅.

19. y( x₂, x₁, x₀ ) = M₃ M₆ M₇.

20. y( x₂, x₁, x₀ ) = x₁ x₀ .

21. y( x₂, x₁, x₀ ) = .

22. y( x₂, x₁, x₀ ) =( ) .

С помощью карт Карно

Задача минимизации структурной формулы ПФ состоит в том, чтобы получить логическое выражение в минимальной дизъюнктивной нормальной форме (МДНФ) или в минимальной конъюнктивной нормальной форме (МКНФ), соответствующее заданной ПФ и содержащее наименьшее количество инверсий, конъюнкций и дизъюнкций и наименьшее число переменных (или их инверсий), над которыми выполняются операции конъюнкции и дизъюнкции.

Суть минимизации ПФ заключается в использовании закона склеивания соседних минтермов, которым на карте Карно соответствуют клетки, заполненные единицами, или соседних макстермов, которым соответствуют нулевые клетки (пустые). Минимизация путем склеивания единичных или нулевых клеток карт Карно (диаграмм Вейча) при небольшом числе переменных выполняется просто и наглядно.

Введем понятие подкуба, которое используется в теории ПФ и их минимизации. Подкуб – это совокупность 2ⁱ соседних клеток карты Карно, заполненных единицами (нулями), для которых по крайней мере одна переменная в координатах всех этих 2ⁱ клеток имеет неодинаковые значения (0 и 1). Из определения следует, что подкуб могут образовать 2, 4, 8, 16 и т.д. соседних клетки карты.

Каждый 2ⁱ-клеточный подкуб позволяет при минимизации исключить i переменных – 1, 2, 3, 4 и т.д. Действительно, подкуб, состоящий из двух клеток, соседних по горизонтали или вертикали (рис.2, а, б, в, г) характеризуется тем, что координаты его клеток различаются значением одной переменной, а остальные переменные имеют одинаковое значение. Переменная, значения которой для этих клеток различны (0 и 1), в соответствии

 

с законом склеивания исчезает. Четырехклеточный подкуб содержит клетки, координаты которых различаются значениями двух переменных (рис.3, а, б, в), следовательно, четырехклеточный подкуб позволяет исключить две переменные. Восьмиклеточный подкуб позволяет исключить три переменные (рис.3, г, д).

 

Все минтермы (макстермы), вошедшие в подкуб, склеиваются за один прием. Результатом склеивания таких клеток является получение конъюнктивного терма (если склеиваются единичные клетки) или дизъюнктивного терма (если склеиваются нулевые клетки).

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

неизменное значение в координатах строк и столбцов всех объединяемых клеток; если неизменное значение переменной в координатах равно 1, то в конъюнкции она записывается без инверсии, если равна 0 – то с инверсией.

На рис.2, а, б, в приведены примеры записи контермов для двухклеточных подкубов, а на рис.3, а, б, в, г, д – четырехклеточных ( ) и восьмиклеточных ( ).

МДНФ – есть дизъюнкция контермов.

Пример: МДНФ для ПФ y₉ (рис.3, е) как результат минимизации по единичным значениям функции имеет вид:

. (5)

Дизтерм (дизъюнктивный терм) – результат склеивания соседних макстермов, входящих в подкуб (соседних нулевых клеток). В алгебраическом представлении дизтерм - есть дизъюнкция переменных, имеющих неизменное значение в координатах строк и столбцов всех объединяемых клеток; если неизменное значение переменной в координатах равно 1, то в дизъюнкции она записывается с инверсией, если равна 0 – то без инверсии.

Для ПФ y₉ (рис.3, ж) построенные подкубы имеют следующие дизтермы:

МКНФ – есть конъюнкция дизтермов.

Пример: МКНФ для ПФ y₉ (рис.3, ж) как результат минимизации по нулевым значениям функции имеет вид:

( ) ( ) ( ). (6)

Ранги контермов или дизтермов, которые входят в логическое уравнение МДНФ или МКНФ переключательной функции, в общем случае не одинаковы.

Общие правила минимизации функций, справедливые для любого числа логических переменных:

- прямоугольные области карты Карно, составляющие подкубы, могут состоять из 1, 2, 4, 8, 16 и т.д. только единичных клеток (при получении МДНФ) или только нулевых клеток (при получении МКНФ);

- для подкубов выбирается минимальный вариант их построения на карте Карно, при котором число подкубов минимально, а их размеры максимальны;

- клетки карты Карно могут неоднократно входить в разные подкубы, если это необходимо для увеличения их размеров и уменьшения их количества.

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

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

Формирование подкубов с включением в них факультативных клеток позволяет получать более простые, как правило, структурные формулы МДНФ или МКНФ. Минимизация функции , приведенной на рис.4, а, отличающейся от функции (рис.3, е) только наличием факультативных клеток, показывает, что включение клеток со знаком в подкубы позволяет получить выражение функции:

, (7)

которое существенно проще, чем (5) или (6).

Существенное различие в сложности формул может иметь место и при минимизации неполностью определенной логической функции при использовании единичных клеток и нулевых клеток (МДНФ и МКНФ).

Для функции , приведенной на рис.4, б, объединение нулевых клеток в подкубы и дает минимизированное выражение (МКНФ):

= ( ) ( ). МДНФ для функции (рис.4, в) сложнее: = .

 

Упражнения

Найти МДНФ и МКНФ для заданных логических функций, используя карты Карно.

 

23. y( x₂, x₁, x₀ ) = m₁ m₂ m₅ m₆.

24. y( x₃, x₂, x₁, x₀ ) = m₀ m₁ m₂ m₃ m₇.

25. y( x₂, x₁, x₀ ) = M₃ · M₅ · M₆ · M₇.

26. y( x₃, x₂, x₁, x₀) = ( 0, 1, 2, 3, 7, 8, 9, 11, 12, 13 ).

27. y( x₃, x₂, x₁, x₀ ) = ( 0, 4, 5, 6, 7, 8, 9, 10 ).

28. y( x₂, x₁, x₀ ) = ( 3, 5, ) + ( 0, 7 ).

29. y( x₃, x₂, x₁, x₀) = ( 0, 4, 7, 11, 14 ) + ( 6, 8, 9, 13 ).

30. y( x₃, x₂, x₁, x₀) = ( 5, 7, 9, 10, 11 ) + ( 2, 13, 15 ).

К заданному базису

Если при проектировании логических схем предъявляется требование получения максимального быстродействия, логическая схема строится на основе представления ПФ в нормальной алгебраической форме.

Всего существует 8 нормальных форм представления ПФ. Получим их на примере проектирования мажоритарной логической схемы (мажоритарного элементы) “2 из 3”, пронумеруем и дадим символьное обозначение путем указания операций первого и второго этапов логического преобразования.

Таблица истинности для мажоритарного элемента приведена в табл.2, карта Карно на рис.5. МДНФ для этой функции является первой нормальной формой. Следующие три нормальных формы получим путем последовательного преобразования МДНФ с применением тождеств двойной инверсии и теоремы де-Моргана. МКНФ – пятая нормальная форма, остальные получены путем ее преобразования.

= 1) И / ИЛИ

= 2) И-НЕ / И-НЕ

= 3) ИЛИ / И-НЕ

. 4) ИЛИ-НЕ / ИЛИ

5) ИЛИ / И

= =

= = 6) ИЛИ-НЕ / ИЛИ-НЕ

= = 7) И / ИЛИ-НЕ

= . 8) И-НЕ / И

При проектировании логических схем в зависимости от наличия определенного типа элементов (базиса) используется соответствующая нормальная форма.

1.7. Скобочные формы логических уравнений

Для аналитического представления переключательных функций можно использовать не только нормальные формы, но и так называемые скобочные формы представления функций. Скобочные формы получаются путем тождественных преобразований МДНФ (МКНФ) с использованием скобок, изменяющих порядок (последовательность) логических преобразований. При вынесении общих членов за скобки порядок функции увеличивается.

В практике проектирования логических схем к скобочным формам приходится обращаться в двух случаях: а) когда необходимо уменьшить аппаратные затраты и стоимость при реализации схем на логических элементах; б) когда число переменных и термов велико и реализация функций на основании МДНФ (МКНФ) с использованием стандартных логических элементов (с стандартным числом входов) невозможна.

На рис.6, а представлена карта Карно логической функции, МДНФ которой

y = x₃ x₂ x₁ x₃ x₂ x₀ x₃ x₁ x₀. (8)

Этой функции соответствует логическая схема второго порядка, показанная на рис.6, б. На основании законов дистрибутивности функцию (8) можно представить в форме

y = x₃ [ x₂ ( x₁ x₀ ) x₁ x₀ ], (9)

которой соответствует схема на рис.6, в. В этой схеме максимальное

 

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

Положительное свойство таких схем – меньшая сложность (аппаратные затраты) и стоимость.

Существует несколько способов оценки сложности логических схем: сложность по Квайну, определяемая как суммарное число входов всех логических элементов; сложность, как число логических элементов; сложность как число условных стандартных корпусов микросхем.

Так, суммарное число входов логической схемы четвертого порядка (рис.6, в) равно 10, а логической схемы второго порядка (рис.6, б) – 12.

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

Второй пример необходимости использования скобочной формы ПФ рассмотрим на примере проектирования мажоритарного элемента “2 из 3” в двух вариантах: когда допустимо использовать логические элементы И-НЕ с любым необходимым числом входов и когда можно использовать только 2-входовые логические элементы И-НЕ.

В минимальной ДНФ логическая функция мажоритарного элемента в базисе И-НЕ имеет вид

y = . (10)

Этому уравнению соответствует логическая схема второго порядка рис.7, а, в которой используются 2- и 3-входовые элементы И-НЕ.

Если для реализации схемы разрешается использовать только 2-входовые элементы И-НЕ, то уравнение (10) преобразуется в скобочную форму

y = , (11)

которому соответствует логическая схема четвертого порядка рис.7, б, ко-

 

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

 

Упражнения

31. Для каждой логической функции четырех переменных, заданной в МДНФ, найти возможную ненормальную (скобочную) форму. Сопоставить аппаратные затраты при реализации функции в МДНФ и в скобочной форме:

а) y = x₃ x₂ x₀ x₃ x₁ x₀ ;

б) y = ;

в) y = x₃ x₂ x₀ x₃ x₂ x₁ x₃ x₁ x₀ x₂ x₁ x₀ ;

г) y =

32. Задана логическая функция y = x₃ x₂ x₀ x₃ x₁ x₀ . Определить порядок логической схемы, реализующей данную функцию, и оценить сложность схем при использовании:

а) нормальной формы логического уравнения И / ИЛИ;

б) двухвходовых элементов И, ИЛИ;

в) нормальной формы логического уравнения И-НЕ / И-НЕ;

г) двухвходовых элементов И-НЕ;

д) нормальной формы логического уравнения ИЛИ-НЕ / ИЛИ-НЕ;

е) двухвходовых элементов ИЛИ-НЕ.

 

Комбинационные схемы

Логическая схема (рис.8) с n входами и k выходами реализует систему переключательных функций y₀...y_k-1. Каждая функция y_i (x₀...x_k-1)

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

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

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

Логические элементы (ЛЭ) общего назначения, выпускаемые в виде готовых интегральных логических схем малой степени интеграции. К ним относятся ЛЭ, представленные на рис.9. Они образуют технически полную

 

 

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

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

Преобразователи кодов – дешифраторы, детекторы состояний, шифраторы, преобразователи специальных кодов, ПЗУ и др.

Коммутационные узлы – ключи, мультиплексоры, мультиплексоры-демультиплексоры и др.

Арифметические узлы – схемы контроля на четность, сумматоры, схемы ускоренного переноса, арифметико-логические устройства, числовые компараторы, умножители и др.

Основными задачами изучения КС являются задачи анализа и синтеза этих схем. Задача анализа – нахождение функции, реализуемой конкретной схемой. Задача синтеза – преобразование заданной логической функции к форме, в которой ПФ представлена через логические функции заданных для реализации элементов. Например: через логические функции ЛЭ основного базиса, универсального базиса; через логические функции, реализуемые дешифратором, мультиплексором и т.п.

 

Примеры синтеза и анализа комбинационных схем

 

Узел свертки по четности

Сверткой по четности цифрового кода (слова) x₃, x₂, x₁, x₀ называется логическое преобразование вида . Для n-разрядных кодов преобразование для функции p записывается аналогично. Логическая функция p является признаком четного число единиц в коде. Если число единиц четное, то p = 1, если – нечетное, то p = 0 (в истинности этого утверждения можно убедиться методом перебора вариантов).

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

Общая схема организации контроля по четности показана на рис.20. Источник данных для каждой кодовой комбинации (для n-разрядного цифрового слова) формирует признак четности, который в качестве дополнительного (n+1)-го разряда отправляется вместе с передаваемым словом в канал передачи данных. Передаваемое (n+1)-разрядное слово имеет всегда нечетное число единиц. Если в исходном коде число единиц было нечетным, то на выходе КС1 значение контрольного разряда p = 0 не меняет число единиц при передаче слова. Если же число единиц в исходном коде было четным, то контрольный разряд для такого кода p =1, и результирующее число единиц в передаваемом (n+1)-разрядном слове

станет нечетным. На приемном конце канала от полученного (n+1)-разрядного слова снова берется свертка по четности e. Если значение этой свертки равно 1, то или в передаваемом слове, или в контрольном разряде при передаче произошла ошибка.

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

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

 

Упражнения

33. Синтезировать одноразрядный арифметический полный сумматор на ЛЭ основного базиса. Оценить сложность схемы и сравнить с вариантом схемы сумматора на рис.17, д.

34. Синтезировать преобразователь двоичного кода 8-4-2-1 в код Грея на логических элементах Исключающее ИЛИ.

35. Получить логическую схему свертки по четности для байта данных.

36. Синтезировать дешифратор в соответствии с таблицей истинности на ЛЭ основного базиса:

37. а) синтезировать преобразователь кода на логических элементах основного базиса. Входной код - двоично-десятичный (двоичные 4-разрядные числа Q₃Q₂Q₁Q₀, эквивалентные десяти десятичным цифрам), выходной код – 7-разрядный код управления 7-сегментным индикатором.

Система логических функций сегментов индикатора:

s₁ = ( 1, 4 ) + ( 10, 11, 12, 13, 14, 15 ),

12345678Следующая ⇒

Поделиться: