Главная Учебники - Разные Лекции (разные) - часть 34
|
Введение Глава 1. Представление данных в цифровых автоматах (ЦА) 1.1 Представление чисел в позиционных системах счисления (ПСС) 1.2 Формы представления данных в ЦА 1.3 Выполнение арифметических операций с целыми числами, представленными в машинных кодах 1.4 Выполнение логических операций с целыми числами, представленными в машинных кодах Глава 2. Методы контроля работы ЦА 2.1. Корректирующая способность кодов 2.2 Метод четности / нечетности. Коды Хеминга 2.3 Контроль по модулю Глава 3. Построение алгоритма реализации численного метода «быстрой сортировки» 3.1 Математическое описание метода 3.2 Таблица используемых переменных Список используемых источников Приложение 1. Блок-схема алгоритма Введение
В своей курсовой работе я ставлю следующие задачи: – научиться представлять данные в ЦА; – изучить методы контроля работы ЦА и научиться строить код Хемминга; – изучить реализацию алгоритма численного метода «быстрой сортировки» и построить его блок-схему. Глава 1. Представление данных в цифровых автоматах (ЦА)
1.3
Представление чисел в позиционных системах счисления (ПСС)
Система счисления – это совокупность символов и правил их записи, необходимых для записи чисел. В позиционной системе счисления вес символа зависит от позиции в которой расположен символ. Например, число 222 – первый символ этого числа имеет вес 200, второй – 20, третий – 2. Основной характеристикой ПСС является основание. Основание ПСС – это количество символов данной системы счисления, которые используются при составлении чисел. В зависимости от основания ПСС существует четыре основных системы счисления: двоичная, восьмеричная, десятеричная и шестнадцатеричная. Все эти системы счисления используются в ЦА и каждая имеет свои основные функции. Например, числа, записанные в двоичной системе счисления, используются в ЦА для операций производимых процессором: запись, считывание, сложение и т.д.; числа в шестнадцатеричной системе счисления – для адресации ячеек памяти. Перевод чисел из одной ПСС в другую
При переводе чисел из десятичной
системы счисления в систему с основанием P
обычно используют следующий алгоритм: 1) если переводится целая часть числа, то она делится на P
, после чего запоминается остаток от деления. Полученное частное вновь делится на P
, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P
выписываются в порядке, обратном их получению; 2) если переводится дробная часть числа, то она умножается на P
, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P
и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P
. Перевод числа из системы счисления с основанием P1
в систему счисления с основанием P2
, можно выполнить по такому же алгоритму, но все вычисления нужно проводить в системе счисления с основанием P1
. Второй способ перевести число можно в два этапа: переведя это число в десятеричную систему счисления, а затем из десятеричной в систему счисления с основанием P2
. Чтобы перевести число из системы счисления с основанием P
Чтобы перевести число из двоичной
системы счисления Чтобы перевести число из восьмеричной
(шестнадцатеричной
) системы счисления в двоичную систему счисления, нужно заменить каждую цифру числа соответствующими им тройками (четверками) двоичных цифр. Задание.
Осуществить перевод числа (А+В), представленного в 10-ой системе из одной системы счисления в другие, по схеме рисунка. ( )16
( )8
( )2
( )2
( )10
( )2
( )16
( )8
( )8
( )10
( )10
( )16
Решение.
А+В=307+6.6=313.610
313.610
= ( )2
Сначала переводим целую часть числа, делим на основание 2: 313/2=156 остаток – 1; 156/2=78 остаток – 0; 78/2=39 остаток – 0; 39/2=19 остаток – 1; 19/2=8 остаток – 1; 9/2=4 остаток – 1; 4/2=4 остаток – 0; 2/2=1 остаток – 0; Дальше делить нельзя, поэтому собираем все остатки, начиная с конца и учитываем конечный результат от деления т.е. 2/2=1. Получим 31310
=1001110012
Теперь переводим дробную часть числа, умножаем на основание 2: * 6 * 2 * 4 * 8 2 2 2 2 1 2 0 4 0 8 1 6 Получим 0.610
= 0.10012
, значит, 31310
» 100111001.10012
100111001.10012
= ( )8
Разобьем число на тройки цифр: 100 111 001. 100 100 , заменим тройки цифр на соответствующими им восьмеричными цифрами т.е. 1002
=48
; 1112
=78
; 0012
=18
. Получим 100111001.10012
=471.448
100111001.10012
= ( )10
1 0 0 1 1 1 0 0 1 . 1 0 0 1 Число 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 Разряды числа 100111001.10012
= 1*2-4
+ 1*2-1
+ 1*20
+ 1*23
+ 1*24
+ 1*25
+ 1*28
= = 0.0652 + 0.5 + 1 + 8 + 16 + 32 + 256 = 313.565210
» 313.610
100111001.10012
= ( )16
Разобьем число на четверки цифр: 0001 0011 1001. 1001 , заменим четверки цифр на соответствующими им шестнадцатеричными цифрами т.е. 00012
=116
; 00112
=316
; 10012
=916
. Получим 100111001.10012
=139.916
313.610
= ( )8
Сначала переводим целую часть числа, делим на основание 8: 313/8=39 остаток – 1; 39/8=4 остаток – 7. Получим 31310
=4718
Теперь переводим дробную часть числа, умножаем на основание 8: * 6 * 8 * 4 * 2 8 8 8 8 4 8 6 4 3 2 1 6 Получим 0.610
= 0.46318
, значит, 31310
» 471.46318
471.46318
= ( )2
Каждый символ числа 471.46318
запишем в двоичной системе счисления: 48
=1002
; 78
=1112
; 18
=0012
; 68
=1102
; 38
=0112
. Получим 471.46318
= 100111001.1001100110012
471.46318
= ( )10
4 7 1 . 4 6 3 1 Число 2 1 0 -1 -2 -3 -4 Разряды числа 471.46318
= 1*8-4
+ 3*8-3
+ 6*8-2
+ 4*8-1
+ 1*80
+ 7*81
+ 4*82
= = 0.0002 + 0.0058 + 0.0937 + 0.5 + 1 + 56 + 256 = 313.599710
» 313.610
471.46318
= ( )16
Перевод числа из восьмеричной системы счисления в шестнадцатеричную проведем в два этапа: сначала переведем число в десятеричную систему счисления, затем из десятеричной в шестнадцатеричную. Перевод числа 471.46318
в десятеричную систему счисления уже осуществлен выше: 471.46318
= 313.610
. Далее переведем 313.610
в шестнадцатеричную систему счисления: 313.610
= ( )16
Сначала переводим целую часть числа, делим на основание 16: 313/16=19 остаток – 9; 19/16=1 остаток – 3. Получим 31310
=13916
Теперь переводим дробную часть числа, умножаем на основание 16: * 6 * 6 16 16 9 6 9 6 Получим 0.610
= 0.9916
, значит, 31310
» 139.9916
139.9916
= ( )2
Каждый символ числа 139.9916
запишем в двоичной системе счисления: 116
=00012
; 316
=00112
; 916
=10012
. Получим 139.9916
= 100111001.100110012
139.9916
= ( )8
Перевод числа из шестнадцатеричной системы счисления в восьмеричную будем выполнять в один этап, делая все вычисления в шестнадцатеричной системе счисления. Сначала переводим целую часть числа, делим на основание 8: 139 8 100 27 – 39 38 1 27 8 20 4 7 Дальше делить нельзя, поэтому собираем все остатки, начиная с конца и учитываем конечный результат от деления т.е. 20/8=4. Получим 13916
= 4718
Теперь переводим дробную часть числа, умножаем на основание 8: * 99 * С8 * 40 8 8 8 4 С8 6 40 2 00 Получим 0.9916
= 0.46208
, значит, 139.9916
» 471.46208
139.9916
= ( )10
1 3 9 . 9 9 Число 2 1 0 -1 -2 Разряды числа 139.9916
= 9*16-2
+ 9*16-1
+ 9*160
+ 3*161
+ 1*162
= 0.0351 + 0.5625 + 9 + 48 + 256 = 313.597610
» 313.610
Выполнение арифметических операций над числами, представленными в ПСС
Операции над числами в двоичной, восьмеричной, шестнадцатеричной системе счисления выполняются по тем же правилам, что и арифметические операции над числами в десятеричной системе счисления. Задание
А) Сложить числа (А)16
и (В)16
(А)10
= 30710
= 13316
(В)10
= 6.610
= 6.9916
+ 133.00 6.99 139.99 Б) Вычесть из числа (А)8
число (В)8
(А)10
= 30710
= 4638
(В)10
= 6.610
= 6.468
– 463.00 6.46 454.31 В) Умножить числа (С)2
и (В)2
(С)10
= 9110
= 10110112
(В)10
= 6.610
= 110.10012
* 1011011 110.1001 1011011 + 1011011000 101101100000 1011011000000 1001010101.0011 В) Разделить число (С)2
на (В)2
(С)10
= 9110
= 10110112
(В)10
= 6.610
= 110.12
1011011 110.1 Þ 10110110 1101 01101 1110.0 010011 001101 0001101 0001101 0000000 1.2
Формы представления данных в ЦА
Кодирование и формы представления чисел в ЦА
Представление чисел в машинных кодах для выполнения арифметических операций
Прямой код – это двоичный код числа, записанный в разрядной сетке, в старшем разряде которого указывается знак числа. Для положительных чисел прямой код числа совпадает с обратным и дополнительном кодом т.е. [A]пр
= [A]обр
= [A]доп
. В противном случае, когда число отрицательное: – обратный код получается из прямого, путем инверсии всех разрядов, за исключением знакового; – дополнительный код получается путем прибавления единицы к обратному коду т.е. [A]доп
= 1 + [A]обр
. Модифицированный обратный (дополнительный) код – аналог обратного (дополнительного) кода, с той лишь разницей, что на знак выделяются два старших разряда. Задание.
Числа А, –А, С и –С представить в прямом, обратном, дополнительном, модифицированном обратном и модифицированном дополнительном кодах. А = 30710
= 1001100112
С = 9110
= 10110112
[A]пр
= [A]об
= [A]доп
= 0|000000100110011 [A]мод
.об
= 00|00000100110011 [A]мод
.доп
= 00|00000100110011 [–A]пр
= 1|000000100110011 [–A]об
= 1|111111011001100 [–A]мод
.об
= 11|11111011001100 [–A]доп
= 1|111111011001100+1 = 1|111111011001101 [–A]мод
.доп
= 11|11111011001100+1 = 11|11111011001101 [C]пр
= [C]об
= [C]доп
= 0|000000001011011 [C]мод.об
= 00|00000001011011 [C]мод.доп
= 00|00000001011011 [–C]пр
= 1|000000001011011 [–C]об
= 1|111111110100100 [–C]мод.об
= 11|11111110100100 [–C]доп
= 1|111111110100100+1 = 1|111111110100101 [–C]мод.доп
= 11|11111110100100+1 = 11|11111110100101 Представление чисел в формате с фиксированной запятой
Для чисел, представленных в формате с фиксированной запятой, предварительно определяется место запятой между разрядами, поэтому число может быть определено только в определенном диапазоне. Если рассматривать два числа, у которых место положения различны, то числа выравниваются по младшему разряду. Для этого все числа заносимые в ЦА предварительно умножаются на маштабный коэффициент. Например: 111.101 * 24
= 1111010 – целый вид; 111.101 * 2–3
= 0.111101 – дробный вид, где 24
и 2–3
– маштабный коэффициент. Задание.
Числа A, –A, B и –B представить в формате с фиксированной точкой (в 16-ти разрядах). При этом числа A и B привести к целому виду, а –A и –B к дробному с 4-мя знаками после запятой. А = 30710
= 1001100112
A = 0000000100110011 – целый вид; A = 100110011*2–4
= 000000010011.0011 – дробный вид. В = 6.610
= 110.12
B = 110.1*21
= 0000000000001101 – целый вид; B = 110.1*2–3
= 000000000000.1101 – дробный вид. Представление чисел в формате с плавающей запятой
Любое число N в системе счисления с основанием q
можно записать в виде N=M*
qp
, где M
называется мантиссой числа, а p
– порядком. Такой способ записи чисел называется представлением с плавающей точкой. Мантисса должна быть правильной дробью, первая цифра дробной части которой отлична от нуля: M
из диапазона [0.1; 1). Такое, наиболее выгодное для компьютера, представление вещественных чисел называется нормализованным. Мантиссу и порядок q
-ичного числа принято записывать в системе с основанием q
, а само основание – в десятичной системе. При хранении числа с плавающей точкой отводятся разряды для мантиссы, порядка, знака числа и знака порядка: … … Знак порядка Мантисса Порядок Например: 753.15 = 0.75315*103
. Задание
. Числа A, –A, B и –B представить в формате с плавающей точкой. А = 307 = 0.307*103
В = 6.6 =0.66*101
Кодирование и формат представления символьной информации
В большинстве первых компьютеров использовался семибитный код КОИ-7
(код обмена информацией, семизначный). В таком коде можно было закодировать 27
=128 символов. Но с развитием техники это стало довольно неудобно. Новый код был уже восьмибитным и основывался на американском стандартном коде обмена информацией ASCII
(American Standard Code for Information Interchange). В восьмибитном коде можно закодировать уже 28
=256 символов. Этого вполне хватает чтобы без всяких проблем использовать в тексте большие и маленькие буквы русского и латинского алфавитов, знаки препинания, цифры, специальные символы. С недавнего времени был предложен новый стандарт символьного кодирования UNICODE
. Шестнадцать разрядов позволяют обеспечить уникальные коды для 216
=65536 различных символов – этого поля достаточно для размещения в одной таблице символов большинства языков планеты. Задание.
Используя таблицу Windows 12.51, закодировать свои: фамилию и имя (записанные на русском и английском языках). Вписать их в разрядную сетку. Буква Десятиричный код Двоичный код Буква Десятиричный код Двоичный код Ш 216 11011000 S 83 1010011 а 224 11100000 h 104 1101000 б 225 11100001 a 97 1100001 а 224 11100000 b 98 1100010 р 240 11110000 a 97 1100001 о 238 11101110 r 114 1110010 в 226 11100010 o 111 1101111 v 118 1110110 П 207 11001111 а 224 11100000 P 80 1010000 в 226 11100010 a 97 1100001 е 229 11100101 v 118 1110110 л 235 11101011 e 101 1100101 l 108 1101100 1.3 Выполнение арифметических операций с целыми числами, представленными в машинных кодах
Арифметические операции с целыми числами, представленными в машинных кодах, выполняются только операцией сложения. Т.е. операция разности, заменяется операцией сложения, операция произведения также заменяется операцией сложения. Например, вычислить: А + B, A – B, –A – B. Пусть А=16010
, B=4510
. [A]доп
= 0|000000010100000 [–A]доп
= 1|111111101100000 [B]доп
= 0|000000000101101 [–B]доп
= 1|111111111010011 А + B A – B –A – B + 0|000000010100000 + 0|000000010100000 + 1|111111101100000 0|000000000101101 1|111111111010011 1|111111111010011 0|000000011001101 0|000000001110011 1|111111100110011 Задание.
Произвести сложение чисел, представленных в машинных кодах: A+C; –A+C; A+(– C); –A+(– C). A = 30710
=1001100112
С = 9110
= 10110112
[A]доп
= 0|000000100110011 [–A]доп
= 1|111111011001101 [C]доп
= 0|000000001011011 [–C]доп
= 1|111111110100101 А + C –A + C + 0|000000100110011 + 1|111111011001101 0|000000001011011 0|000000001011011 0|000000110001110 1|111111100101000 А + (– C) –A + (– C) + 0|000000100110011 + 1|111111011001101 1|111111110100101 1|111111110100101 0|000000011011000 1|111111001110010 1.4 Выполнение логических операций с целыми числами, представленными в машинных кодах
Количество логических операций может быть вычисленно по формуле Для выполнения логических операций, используют таблицы истинности:Логическое сложение a Ú b Логическое умножение a & b Логическое отрицание Сложение по модулю 2 a Å b a \ b 1 0 a \ b 1 0 a a \ b 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 Задание:
а) произвести логическое сложение чисел А и С: Ú 0|000000100110011 0|000000001011011 0|000000101111011 б) произвести логическое умножение чисел А и С: & 0|000000100110011 0|000000001011011 0|000000000010011 в) произвести сложение чисел А и С по модулю 2. Å 0|000000100110011 0|000000001011011 0|000000101101000 г) произвести логический сдвиг: влево для чисел А и –А, вправо для С и –С A –A 0|000000100110011 1|111111011001101 Число 0|000001001100110 1|111110110011010 Результат сдвига влево C –C 0|000000001011011 1|111111110100101 Число 0|000000000101101 0|111111111010010 Результат сдвига вправо д) произвести логический циклический сдвиг: влево для чисел А и –А, вправо для чисел С и –С A –A 0|000000100110011 1|111111011001101 Число 0|000010011001100 1|111101100110100 Результат сдвига влево на 2 бита C –C 0|000000001011011 1|111111110100101 Число 0|000000000010110 0|011111111101001 Результат сдвига вправо на 2 бита e) произвести арифметический сдвиг: влево для чисел А и –А, вправо для чисел С и –С A –A 0|000000100110011 1|111111011001101 Число 0|000001001100110 1|111110110011010 Результат сдвига влево C –C 0|000000001011011 1|111111110100101 Число 0|000000000101101 1|011111111010010 Результат сдвига вправо Глава 2. Методы контроля работы ЦА
2.1 Корректирующая способность кодов
При работе ЦА могут произойти те или иные сбои, приводящие к искажению информации. Поэтому при проектировании ЦА должны предусматриваться средства, позволяющие контролировать, выявлять и исправлять возникающие ошибки. Решение всех задач контроля становится возможным только при наличии определенной избыточности информации, которая сопровождает основную информацию. Иначе говоря, при представлении числа в каком-либо коде, необходимо предусмотретьв этом коде дополнительные (контрольные) разряды. Систематический код – это код, содержащий в себе информационные и контрольные разряды. В контрольные разряды записывается некоторая информация об исходном числе, поэтому систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов – k
, а относительная избыточность – Понятие корректирующей способности кода связывают с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Корректирующая способность кода связана понятием кодового расстояния. Кодовое расстояние (Хемингово расстояние) d для кодовых комбинаций A и B определяется как вес такой третьей комбинации, которая получается сложением исходных комбинаций по модулю 2. Вес кодовой комбинации V – это количество единиц содержащихся в кодовой комбинации. Например, A=100111001 и B=011011100. Отсюда веса кодовых комбинаций будут равны: V(A)=5, V(B)=5. Кодовая комбинация C=A+B=111100101, вес этой кодовой комбинации равен V(C)=6. Таким образом кодовое расстояние для A и B – d(A,B)=V(C)=6. В любой позиционной системе счисления минимальное кодовое расстояние равно 1. В теории кодирования показано, что систематический код обладает способностью обнаружения ошибки только тогда, когда код расстояния для него больше или равен 2t. Следовательно, 2.2 Метод четности / нечетности. Коды Хеминга
Если в математическом коде выделен один контрольный разряд, то к каждому двоичному числу добавляется один избыточный разряд. В этот разряд записывается 1 или 0 с таким условием, чтобы сумма цифр по модулю 2 была равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнруживается по нарушению четности / нечетности. При таком кодировании допускается, что может возникнуть только одна ошибка. Пример реализации метода четности: Число Контрольный разряд Проверка 10101011 1 0 11001010 0 0 10010001 1 0 11001011 0 1 – ошибка Можно представить и несколько видоизмененный способ контроля по методу четности / нечетности. Длинное слово разбивается на группы, каждая из которых содержит n
разрядов. Контрольные разряды – k
, выделяются всем группам по строкам и столбцам согласно следующей схеме: Увеличение избыточности приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить ее. Например: число 1000111011010101110010101 представим по указанной выше схеме, получим: 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 Теперь, если при передаче было получено число: 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 Тогда проверка показывает, что ошибка возникла в информации третьей строки и четвертого столбца. Следовательно, разряд, содержащий ошибочную информацию, находится на пересечении третьей строки и четвертого столбца. Ошибку можно устранить изменив 0 на 1. Код Хэмминга – биочный систематический код, то есть состоящий из информационных и корректирующих символов, рассположенных по строго определенной системе, имеющих одинаковую длину и всегда занимающих строго определенные места в кодовых комбинациях. При передаче кода может быть искажен или не искажен любой символ. Если длина кода – n
символов, то Соотношение n
, Таблица 2.2.a n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 1 1 2 3 4 4 5 6 7 8 9 10 11 11
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 Пусть необходимо передать число 1110
=10112
. Значит Далее необходимо определить на какой позиции должны находиться контрольные коэффициенты. Позиция контрольных коэффициентов – k
в коде вычисляется по формуле – Таблица 2.2.c 1 2 3 4 5 6 7 Разряды кода Хемминга k1 k2 И4 k3 И3 И2 И1 Назначение разрядов 1 0 1 1 Значение разряда Где ki
– контрольный коэффициент (отсчет идет слева на право); Иi
– информационный символ (отсчет идет справа на лево). Значение контрольных коэффициентов по правилу: если сумма единиц на проверочных позициях четная, то значение контрольного коэффициента равно 0, в противном случае – 1. Таблица 2.2.d Позиция контрольного коэффициента Проверочные позиции 1 1, 3, 5, 7, 9, 11, 13…
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||