Арифметические и логические основы цифровой техники.

Арифметические и логические основы цифровой техники.

Системы исчисления.

Системы исчисления бывают позиционные и не позиционные.

• Непозиционные – значение цифры не зависит от позиции в числе.

Например: римские цифры. I I I

• Позиционные – значение цифры зависит от позиции в числе.

1, 11, 111

Основание системы счисления – P, P>1

а₁, а₂,…,а_р – символы алфавита

А – любое число

А= а_nРⁿ + а_n-1Р^n-1 + …+ а₁Р¹ + а₀Р⁰

Если дробное число, то:

А= а_nРⁿ + а_n-1Р^n-1 + …+ а₁Р¹ + а₀Р⁰ + а_-1Р^-1 + а_-mР^-m

А=

Число выглядит так: а_nа_n-1…а₁а₀а_-1...а_-m

Рассмотрим пример: 8 2 1, 3 5

а₂ а₁ а_{0 ,} а_-1 а_-2

Оптимальная система исчисления.

N – число чисел

n – число разрядов в числе

N=Pⁿ где n=log_PN

С – аппаратные затраты – денежное выражение нашей схемы.

С ~ Р·n=Р· log_PN

Минимум функции будет при условии: Р=2,71…, т. е. Р=exp

Т. к. Р – целое, то Р=3 – система оптимальная.(минимальные затраты) Но, она сложна в изготовлении.

Рассмотрим пример. Пусть есть n разрядов, каждый разряд принимает 10 значений, следовательно это десятичная система. При троичной системе каждый разряд будет принимать три значения (0, 1, 2). Но такое устройство более сложное в изготовлении чем, например, при Р=2 (принимает значения - 0,1)

На практике применяют Р=2.

Р=10 в 1,5 раза сложнее, чем Р=2, следовательно затрат больше.

Чем меньше система счисления, тем больше разрядов.

			A
			B
			C
			D
			E
			F

Двоичная арифметика.

Для суммы:

0+0=0

0+1=1

1+0=1

1+1=10, где 0 – это сумма S, 1 – это перенос CR

Числа будут записываться как: 00, 01, 01, 10

Таблица истинности:

Для S

Для CR

Для разности:

0-0=0

1-0=1

1-1=0

10-1=1 где 1 – это заем

Таблица истинности:

Для разности

Для заема

Для умножения:

0·0=0

0·1=0

1·0=0

1·1=1

Таблица истинности:

Для деления:

0:1=0

1:1=1

Перевод чисел из одной системы в другую.

• 8=2³

16=2⁴

Примеры: 305,4₈ = 011 000 101, 100_2, где нижние индексы указывают на систему счисления

305,4₁₆ = 0011 0000 0101, 01₂

5F1C, EE₁₆ = 0101 1111 0001 1100, 1110 1110₂

001010111, 110110100₂ = 127, 664₈

01010111, 1101 1010₂ = 57, DA₁₆

• Система Р и h

А=

2Е5, А₁₆ = (2·16² + 14·16¹ + 5·16⁰ + 10·16^-1)₁₀ = 741, 625

52₁₀ = 101·1010¹ + 10·1010⁰ = 110100₂

• А = b_n·b_n-1…b₁·b₀ = b_n·hⁿ + … + b₁·h¹ + b₀ = (b_n·h^n-1 +… + b₁)·h + b₀ = A₁·h +b₀

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

Рассмотрим пример:

70₁₀ нужно перевести в двоичную систему

Следовательно, получаем 1000110

70₁₀ нужно перевести в «8» систему

Получаем 106

Представление положительных и отрицательных чисел.

Прямой код числа.

Рассмотрим число 0110:

· Если «+», то 0' 0110

Где 0 показывает что число «+»

· Если «-», то 1' 0110

Где 1 показывает что число «-»

+0, 0101 запишется как 0,0101

-0, 0101 запишется как 1,0101

Обратный код числа.

	Прямой код	Обратный код	дополнительный
+0110
-0101
+0, 0101	0, 0101	0, 0101	0, 0101
-0, 0101	1, 0101	1, 1010	1, 1011

Обратный код – дополнение до единицы

Дополнительный код – дополнение до двух

Обратный код в сумме с исходным дает 1, а дополнительный в сумме с исходным дает 0.

	Обратный код	Дополнительный код
-1
-2
-3
-4
-5
-6
-7

Правило сложения для обратного кода: при сложении чисел в обратном коде знаковые разряды складываются аналогично остальным.

Перенос из знакового разряда добавляется к младшему разряду результата.

Правило сложения для дополнительных кодов: при сложении чисел в дополнительном коде знаковые разряды складываются аналогично остальным.

Перенос из знакового разряда теряется, а результат получается в дополнительном коде.

Примеры: в дополнительном коде

· +4+3=+7

0100+0011=0111

· 1+(-3)=-2

0001+1101=1110

В обратном коде

· 7+(-3)=4

0111+1100=0100

Весовые коды.

, где Рⁱ это вес

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

Для кодировки десятичных чисел в двоичные:

d = W₃·b₃ + W₂·b₂ + W₁·b₁ + W₀·b₀

d - десятичная цифра

W – вес данного разряда

b – двоичные цифры

В данном примере 4 двоичных цифры, а это 16 возможных разрядов. Нам надо использовать только 10, следовательно 6 избыточных.

Число вариантов кодировки:

Существуют не весовые коды, которые не подчиняются данной функции.

Самые распространенные весовые коды: 8421, 7421, 7321, 6421, 6321, 5311, 4421,

8 4 2 1 – двоично-десятичный код

W₃ W₂ W₁ W₀

Пример: запишем 6₁₀ в коде 8421

6₁₀ = 8·0 + 4·1 + 2·1 + 1·0 = 0110₈₄₂₁

6₁₀ = 0111₇₃₂₁

6₁₀ = 0110₆₄₂₁

Код 8421 совпадает с двоичным, если кодируем числа от 0 до 9.

Весовые коды могут быть отрицательными.

Код 8421 – дополняющийся двоично-десятичный код. Его два младших разряда отрицательные (2 и 1)

9₁₀ = 1111₈₄₂₁ = 8·1 + 4·1 – 2·1 - 1·1

Правила составления весовых кодов.

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

· Вес младшего разряда должен быть единица, иначе мы не сможем закодировать единицу.

· Вес второго разряда должен быть один или два.

· Сумма двух старших разрядов должна быть больше либо равна 6, если второй разряд двойка, или 7, если второй разряд единица.

Существуют не весовые коды.

Код 8421 часто используется на практике.

Правила сложения чисел в двоично-десятичном коде (ДДК)

• Если результат получается от 0 до 9, то сложение как двоичных чисел.
• Если результат от 10 до 15, то необходимо произвести коррекцию (добавление 6) и возникающий перенос переносится в старшую тетраду.
• Если результат от 16 до 18, то перенос нужно перенести в старшую тетраду, а потом сделать коррекцию.

Другие виды кодов.

1. Самодополняющиеся коды.

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

Пример: 5₁₀ + 4₁₀ = 9₁₀

1011₈₄₂₁ + 0100₈₄₂₁ = 1111₈₄₂₁

Коды 2421 и +3 это самодополняющиеся коды.

Код +3 получается из кода 8421 добавлением тройки. Это непозиционный код. Удобен для вычисления

5₁₀ = 1000₊₃

4₁₀ = 0111₊₃

0₁₀ = 0011₊₃

9₁₀ = 1100₊₃

Свойства сложения чисел в коде +3:

· Сложение происходит тетрадами, т. е. по четыре разряда

· Если при сложении есть перенос, то производится коррекция (прибавление 3)

· Если нет переноса, то производится коррекция с вычитанием тройки.

1. Код Грея.

Это циклический код. Код Грея двух разрядный, у него всегда меняется один разряд. Непозиционный код.

Используется в системах передачи информации.

Код Грея:

Четырех разрядный код Грея:

1. Код 2 из 5

5 разрядов из них лишь два истинные.

1. Код Джонсона

1. Код бикварный.

Это весовой код.

1. Код 51111

Обнаружение и исправление ошибок в кодах.

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

d=2 между точками 110 и 011

d=1 между соседними точками.

Это кодовое расстояние можно использовать как способ обнаружения ошибки.

Кратность ошибки – (d_min - 1)

Если изменилось два бита, то двукратной ошибки не обнаружить.

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

Пусть у нас есть число 1011, добавим бит четности, следовательно, получим - 11011 – четное число.

Ошибки при передачи информации возникают всегда.

Пример: у нас есть диск; там 16 битное кодирование, чтобы записать и считать без ошибок добавляется 6 бит, следовательно, получается 22 бита. Это код Рида – Соломона.

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

Самое оптимальное кодирование при использовании кода Хэмминга.

Рассмотрим исключающее ИЛИ.

а	b

Х = a b

Бит четности: Р = A B C D

Правила для построения кода Хэмминга:

• Для определенного количества комбинаций двоичных чисел n, определяется число контрольных битов r.

m = n - r

n – общее число в коде Хэмминга

m – сама информация

• Контрольные биты занимают позиции I = 1, 2, 4, 8, а биты информации занимают оставшиеся позиции: a₃, a₅, a₆, a₇, a₉, a₁₀
• Вводятся специальные коэффициенты – С

Р – контрольный бит. Он должен быть таким, чтобы сумма единиц с ним была четной.

С₀ = Р₁ а₃ а₅ а₇ а₉ а₁₁ а₁₃ а₁₅ = 0

С₁ = Р₂ а₃ а₆ а₇ а₁₀ а₁₁ а₁₄ а₁₅ = 0

С₂ = Р₄ а₅ а₆ а₇ а₁₂ а₁₃ а₁₄ а₁₅ = 0

С₃ = Р₈ а₉ а₁₀ а₁₁ а₁₂ а₁₃ а₁₄ а₁₅ = 0

Если все С = 0, то передача информации прошла без ошибок.

Если хотя бы одно из С не равно 0, то произошла ошибка.

Для обнаружения ошибки существует формула:

N = С_r-1·2^r-1 + … + C₂·2² + C₁·2 + C₀, где N – номер позиции где произошла ошибка.

Пример: 1001₂, код 8421

Х3	Х5	Х6	Х7

m=4, r=3, n=8

Р₁Р₂Х₃Р₄Х₅Х₆Х₇

Р₁=0, Р₂=0

Р₄=0 1 0=1

0011001_Хэм

Дата добавления: 2015-10-21