Загрузка...
Учебная работа. Курсовая работа: Цифровые автоматы
Введение
Глава 1. 1.2 Формы представления данных в ЦА
1.3 Выполнение арифметических операций с целыми числами, представленными в машинных кодах
1.4 Выполнение логических операций с целыми числами, представленными в машинных кодах
Глава 2. способы контроля работы ЦА
2.1. Корректирующая способность кодов
2.2 способ четности / нечетности. Коды Хеминга
2.3 Контроль по модулю
Глава 3. Построение метода реализации численного способа «резвой сортировки»
3.1 Математическое описание способа
3.2 Таблица применяемых переменных
Перечень применяемых источников
приложение 1. Блок-схема метода
Введение
В собственной курсовой работе я ставлю последующие задачки:
– научиться представлять данные в ЦА;
– изучить способы контроля работы ЦА и научиться строить код Хемминга;
– изучить реализацию метода численного способа «резвой сортировки» и выстроить его блок-схему.
Глава 1. совокупа знаков и правил их записи, нужных для записи чисел.
В позиционной системе счисления вес знака зависит от позиции в какой размещен знак. к примеру, число 222 – 1-ый знак этого числа имеет вес 200, 2-ой – 20, 3-ий – 2.
Главный чертой ПСС является основание. Основание ПСС – это количество знаков данной системы счисления, которые употребляются при составлении чисел. Зависимо от основания ПСС существует четыре главных системы счисления: двоичная, восьмеричная, десятеричная и шестнадцатеричная. Все эти системы счисления употребляются в ЦА и любая имеет свои главные функции. к примеру, числа, записанные в двоичной системе счисления, употребляются в ЦА для операций производимых микропроцессором: запись, считывание, сложение и т.д.; числа в шестнадцатеричной системе счисления – для адресации ячеек памяти.
Перевод чисел из одной ПСС в другую
При переводе чисел
системы счисления в систему с основанием
обычно употребляют последующий метод:
1) если переводится целая часть числа, то она делится на
, опосля чего же запоминается остаток от деления. Приобретенное личное вновь делится на
, остаток запоминается. Процедура длится до того времени, пока личное не станет равным нулю. Остатки от деления на
выписываются в порядке, оборотном их получению;
2) если переводится дробная часть числа, то она множится на
, опосля чего же целая часть запоминается и отбрасывается. Вновь приобретенная дробная часть множится на
и т.д. Процедура длится до того времени, пока дробная часть не станет равной нулю. Целые части выписываются опосля двоичной запятой в порядке их получения. Результатом быть может или конечная, или повторяющаяся двоичная дробь. Потому, когда дробь является повторяющейся, приходится обрывать умножение на каком-либо шаге и наслаждаться приближенной записью начального числа в системе с основанием
.
Перевод числа из системы счисления с основанием
в систему счисления с основанием
, можно выполнить по такому же методу, но все вычисления необходимо проводить в системе счисления с основанием
. 2-ой метод перевести число можно в два шага: переведя это число в десятеричную систему счисления, а потом из десятеричной в систему счисления с основанием
.
Чтоб перевести число из системы счисления с основанием
систему счисления, необходимо отыскать сумму произведений содержимого разряда на вес этого разряда в системе счисления с основанием
. Где разряд – номер позиции в числе, нумеруются справа влево, начиная с нуля; вес разряда – число, равное основанию системы счисления в степени номера разряда.
Чтоб перевести число
системы счисления
в восьмеричную (шестнадцатеричную) систему счисления, необходимо разбить число на тройки (четверки) цифр, в случае необходимости следует дополнить целую и дробную части числа нулями (целую слева, дробную справа). Потом поменять приобретенные группы цифр надлежащими им восьмеричными (шестнадцатеричными) цифрами. к примеру, число 11010010.102
необходимо перевести в восьмеричную систему счисления. Разобьем число на тройки цифр: 011 010 010. 100 , заменим тройки цифр на надлежащими им восьмеричными цифрами. Получим 11010010.102
= 322.48
Чтоб перевести число
(
) системы счисления в двоичную систему счисления, необходимо поменять каждую цифру числа надлежащими им тройками (четверками) двоичных цифр.
Задание.
Выполнить перевод числа (А+В), представленного в 10-ой системе из одной системы счисления в остальные, по схеме рисунка.
(А+В)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 – дробный вид.
метод записи чисел именуется представлением с плавающей точкой.
Мантисса обязана быть правильной дробью, 1-ая цифра дробной части которой отлична от нуля:
из спектра [0.1; 1).
Такое, более прибыльное для компа, порядок
-ичного числа принято записывать в системе с основанием
, а само основание – в десятичной системе.
При хранении числа с плавающей точкой отводятся разряды для мантиссы, порядка, знака числа и знака порядка:
…
…
символ порядка
Мантисса
порядок
К примеру: 753.15 = 0.75315*103
.
Задание
. Числа A, –A, B и –B представить в формате с плавающей точкой.
А = 307 = 0.307*103
В = 6.6 =0.66*101
Кодирование и формат представления символьной инфы
В большинстве первых компов употреблялся семибитный код
(код обмена информацией, семизначный). В таком коде можно было закодировать 27
=128 знаков. Но с развитием техники это сделалось достаточно неловко.
Новейший код был уже восьмибитным и основывался на южноамериканском обычном коде обмена информацией
(American Standard Code for Information Interchange). В восьмибитном коде можно закодировать уже 28
=256 знаков. Этого полностью хватает чтоб без всяких заморочек применять в тексте огромные и мелкие буковкы российского и латинского алфавитов, знаки препинания, числа, особые знаки.
С недавнешнего времени был предложен новейший эталон символьного кодировки
. Шестнадцать разрядов разрешают обеспечить неповторимые коды для 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 Выполнение логических операций с целыми числами, представленными в машинных кодах
количество логических операций быть может вычисленно по формуле 
, где
– число переменных. Из формулы видно, что для 2-ух переменных a и b логических операций 16. Главные из их: логическое сложение, логическое умножение, логическое отрицание, сложение по модулю 2.
Для выполнения логических операций, употребляют таблицы истинности:Логическое сложение
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 Корректирующая способность кодов
При работе ЦА могут произойти те либо другие сбои, приводящие к искажению инфы. Потому при проектировании ЦА должны предусматриваться средства, дозволяющие надзирать, выявлять и исправлять возникающие ошибки. Решение всех задач контроля становится вероятным лишь при наличии определенной избыточности инфы, которая аккомпанирует основную информацию. По другому говоря, при представлении числа в каком-либо коде, нужно предусмотретьв этом коде доп (контрольные) разряды.
Периодический код – это код, содержащий внутри себя информационные и контрольные разряды. В контрольные разряды записывается некая информация о начальном числе, потому периодический код владеет избыточностью.
При всем этом абсолютная избыточность будет выражаться количеством контрольных разрядов –
, а относительная избыточность – 
, где
– количество информационных разрядов.
Понятие корректирующей возможности кода связывают с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения либо исправления ошибки. Корректирующая способность кода связана понятием кодового расстояния.
Кодовое расстояние (Хемингово расстояние) 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. Как следует, 
, где t – кратность обнаруживаемых ошибок. Это значит, что меж примыкающими кодовыми комбинациями обязана существовать, по последней мере одна кодовая композиция.
2.2 Способ четности / нечетности. Коды Хеминга
Если в математическом коде выделен один контрольный разряд, то к любому двоичному числу добавляется один лишний разряд. В этот разряд записывается 1 либо 0 с таковым условием, чтоб сумма цифр по модулю 2 была равна 0 для варианта четности либо 1 для варианта нечетности. Возникновение ошибки в кодировке обнруживается по нарушению четности / нечетности. При таком кодировке допускается, что может появиться лишь одна ошибка.
Пример реализации способа четности:
Число
Контрольный разряд
Проверка
10101011
1
0
11001010
0
0
10010001
1
0
11001011
0
1 – ошибка
Можно представить и несколько видоизмененный метод контроля по способу четности / нечетности. Длинноватое слово разбивается на группы, любая из которых содержит
разрядов. Контрольные разряды –
, выделяются всем группам по строчкам и столбцам согласно последующей схеме:
Повышение избыточности приводит к тому, что возникает возможность не только лишь найти ошибку, да и поправить ее.
к примеру: число 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
Тогда проверка указывает, что ошибка появилась в инфы третьей строчки и 4-ого столбца. Как следует, разряд, содержащий неверную информацию, находится на пересечении третьей строчки и 4-ого столбца. Ошибку можно убрать изменив 0 на 1.
Код Хэмминга – биочный периодический код, другими словами состоящий из информационных и подкорректирующих знаков, рассположенных по строго определенной системе, имеющих схожую длину и постоянно занимающих строго определенные места в кодовых композициях.
При передаче кода быть может искажен либо не искажен хоть какой знак. Если длина кода –
знаков, то 
– полное количество композиций кода. По методике Хэмминга можно найти число информационных знаков кода, обнаруживающего и корректирующего одиночную ошибку последующим образом:
, где
– число информационных знаков в коде;
– число контрольных знаков;
– длина кода Хемминга.
Соотношение
, и для кода Хэмминга можно представить в виде таблицы:
Таблица 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
. означает 
. Используя таблицу 2.2.a получаем: 
, 
.
Дальше нужно найти на какой позиции должны находиться контрольные коэффициенты. Позиция контрольных коэффициентов –
в коде рассчитывается по формуле – 
, где
– порядковый номер коэффициента
. Получаем 7-разрядный код:
Таблица 2.2.c
1
2
3
4
5
6
7
Разряды кода Хемминга
k1
k2
И4
k3
И3
И2
И1
Предназначение разрядов
1
0
1
1
Где ki
– контрольный коэффициент (отсчет идет слева на право); Иi
– информационный знак (отсчет идет справа на лево).
случае – 1.
Таблица 2.2.d
Позиция контрольного коэффициента
Проверочные позиции
1
1, 3, 5, 7, 9, 11, 13…
2
2, 3, 6, 7, 10, 11, 14…
4
4, 5, 6, 7, 12, 13, 14…
8
8, 9, 10, 11, 12, 13, 14…
Итак, используя таблицу 2.2.d назодим значения контрольных коэффициентов ki
:
k1
= 1 + 0 + 1 = 0;
k2
= 1 + 1 + 1 = 1;
k3
= 0 + 1 +1 = 0.
Получим код Хемминга 0110011 для передачи числа 1110
.
сейчас разглядим пример корректировки приобретенного кодированного в коде Хемминга числа, в каком есть сбой. Получили число 0110001. Для исправления ошибки нужно найти позицию, в какой произошел сбой. Для этого определяем значения контрольных коэффициентов, используя таблицу 2.2.d:
k1
= 0 + 1 + 0 + 1 = 0 – нет ошибки;
k2
= 1 + 1 + 0+ 1 = 1 – ошибка;
k3
= 0 + 0 +0 + 1 = 1 – ошибка.
Номер неверного разряда совпадает с суммой позиций контрольных коэффициентов, указавших на наличие ошибки т.е. 2 + 4 = 6. Для исправления ошибки довольно инвертировать
Задание.
Выстроить код Хемминга для числа А.
A = 30710
= 1001100112
Используя таблицу 2.2.a получаем: 
, 
.
1
2
3
4
5
6
7
8
9
10
11
12
13
Разряды кода Хемминга
k1
k2
И9
k3
И8
И7
И6
k4
И5
И4
И3
И2
И1
Предназначение разрядов
1
0
0
1
1
0
0
1
1
k1
= 1 + 0 + 1 + 1 + 0 + 1 = 0;
k2
= 1 + 0 + 1 + 0 + 0 = 0;
k3
= 0 + 0 +1 + 1 + 1 = 1;
k4
= 1 + 0 + 0 + 1 + 1 = 1.
Получим код Хемминга 0011001110011.
При передаче, получили код с ошибкой 0011001110111. Проверяем:
k1
= 0 + 1 + 0 + 1 + 1 + 1 + 1 = 1; – ошибка;
k2
= 0 + 1 + 0 + 1 + 0 + 1 = 1; – ошибка;
k3
= 1 + 0 + 0 +1 + 1 + 1 = 0; – нет ошибки;
k4
= 1 + 1 + 0 + 1 + 1 + 1 = 1 – ошибка.
Ошибка находится в разряде 1 + 2 + 8 = 11, инвертируем 11-й разряд и получаем начальный код Хемминга.
2.3 Контроль по модулю
Контроль выполнения арифметических и логических операций можно производить при помощи контрольных кодов, представляющих из себя остатки от деления чисел на некий модуль. Таковой контроль именуют контролем по модулю. Для двоичных чисел этот модуль обычно равер либо больше 3. Различают числовой и цифровой контроль по модулю.
При числовом способе код данного числа определяется как меньший положительный остаток от деления числа на избранный модуль. к примеру, найти контрольный код числа 160 по модулю 6. Для этого делим 160 на 6, получаем остаток – 4.
При цифровом способе контроля, контрольный код числа появляется делением суммы цифр числа на избранный модуль. к примеру, найти контрольный код числа 160 по модулю 6. Сумма цифр числа 160 равна 7, делим ее на 6. Получим остаток 1, означает это, контроль числа 160 по модулю 6, при цифровом способе контроля.
Числовой способ контроля
Арифметические операции можно представить в виде последовательности последующих простых операций: передача слова, сдвиг, взятие оборотного кода, сложение.
Операцию сдвига можно представить как передачу слова из i-го разряда в (i+x) разряд. Потому, контроль сдвига можно выполнить по способу четности / нечетности.
Контроль выполнения арифметических операций: сложение, вычитание, умножение можно выполнить способом контроля по модулю. Для этого используют формулы:
KA
= A mod P KB
= B mod P
KA+B
= (A + B) mod P = (KA
+ KB
) mod P
KA*B
= (A * B) mod P = (KA
* KB
) mod P
к примеру, найдем контрольный код чисел A, B и контрольный код арифметических операций над ними, получим:
A
B
A + B
A – B
A * B
Арифметические операции над числами
89
57
146
33
5073
8
3
2
6
6
Контроль по модулю 9
Проверка выполненных операций:
– ошибка, означает эта операция
выполненна не правильно;
KA
+
B
= (8 + 3) mod 9 = 2 – нет ошибки;
KA
–
B
= (8 – 3) mod 9 = 5
KA
*
B
= (8 * 3) mod 9 = 6 – нет ошибки.
Задание.
Найти контрольные коды чисел A и C по модулю P, также контрольные коды суммы A + C и разности A – C.
КА
= 307 mod 9 = 1;
KC
= 91 mod 9 = 1;
KA+C
= (307+91) mod 9 = 398 mod 9 = 2; проверка:
KA
+
C
= (1 + 1) mod 9 = 2 mod 9 = 2 – нет ошибки.
KA
–
C
= (307–91) mod 9 = 216 mod 9 = 0; проверка:
KA
–
C
= (1 – 1) mod 9 = 0 mod 9 = 0 – нет ошибки.
Цифровой способ контроля
Контроль выполнения арифметических операций: сложение, вычитание, умножение производится по темже формулам, лишь при цифровом способе контроля, контрольный код числа появляется делением суммы цифр числа на избранный модуль.
Задание.
Найти контрольные коды чисел A и C по модулю P, также контрольные коды суммы A + C и разности A – C.
КА
= (3+0+7) mod 9 = 1;
KC
= (9+1) mod 9 = 1;
KA+C
= (3+0+7+9+1) mod 9 = 20 mod 9 = 2; проверка:
KA
+
C
= (1 + 1) mod 9 = 2 mod 9 = 2 – нет ошибки.
KA
–
C
= (3+0+7–9–1) mod 9 = 0 mod 9 = 0; проверка:
KA
–
C
= (1 – 1) mod 9 = 0 mod 9 = 0 – нет ошибки.
Глава 3. Построение метода реализации численного способа «резвой сортировки»
3.1 Математическое описание способа
метод сортировки К. Хоора именуют сортировкой с разделением либо «резвой сортировкой». В базу метода положен способ поочередного дробления массива на части.
Метод «резвой сортировки» можно проанализировать на примере. Пусть дан массив M[i] = (9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5). Опосля первого вызова процедуры QuickS в начальном массиве будет определена его середина (10-й элемент) и переменной X присвоено части. Дальше производится обмен элементами по последующему правилу:
Во время просмотра левой части массива слева вправо выполныется поиск такового элемента массива, что M[i]>X, потом во время просмотра правой части справа влево отыскивается таковой элемент, что M[i]<X. Производится обмен местами данных частей, пока все элементы слева от середины, удовлетворяющие условию M[i]>X, не будут обменены с элементами, рассположенными справа от середины и удовлетворяющими условию M[i]<X. В итоге этого получим массив из 2-ух частей последующего вида:
9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5 Число итераций =1
19, 20, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 11, 9, 2, 5 Число итераций =2
19, 20, 20, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =3
19, 20, 20, 19, 19, 1, 5, 17, 10, 18, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =4
19, 20, 20, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =5
Дальше левая часть в свою очередь дробится на две части, и вызывается процедура для сортировки левой части (с 1-го по 6-й элемент)
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =6
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =7
Опосля того как левая часть массива отсортирована, снова рекурсивно вызывается процедура, в какой определяется середина данной части массива, и производится обмен частей. Массив становится таковым:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =8
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =9
Дальше снова рекурсивно вызывается процедура для сортировки, пока в каждой из частей остается по одному элементу.
Потом рекурсивно вызывается процедура для аналогичной сортировки правой части (с 7-го по 13-й элемент). Итог поочередных шагов сортировки массива отображается так:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число итераций =10
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число итераций =11
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число итераций =12
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 3, 3, 5, 9, 12, 12, 11, 1, 2, 5 Число итераций =13
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 3, 5, 9, 12, 12, 3, 1, 2, 5 Число итераций =14
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 5, 9, 12, 3, 3, 1, 2, 5 Число итераций =15
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число итераций =16
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число итераций =17
20, 20, 19, 19, 19, 18, 17, 17, 12, 9, 11, 12, 10, 9, 5, 3, 3, 1, 2, 5 Число итераций =18
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число итераций =19
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число итераций =20
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число итераций =21
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 3, 3, 1, 2, 5 Число итераций =22
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число итераций =23
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число итераций =24
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число итераций =25
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 3, 2, 1 Число итераций =26
Как видно из примера, данный массив будет отсортирован за 26 итераций способом «резвой сортировки». Этот же массив отсортированный линейным способом, будет отсортирован за 190 итераций, пузырьковым способом за 170 итераций. Как видно из приведенных примеров, метод «резвой сортировки» дает наиболее наилучшие результаты.
3.2 Таблица применяемых переменных
имя переменной
Тип переменной
Описание переменной
M[i]
Целый / Вещественный
Сортируемый массив чисел
i
j
Целый
Употребляются в цикле при воззвании к элементу массива
X
Целый / Вещественный
First
Last
Целый
Границы сортируемого массива
tmp
Целый / Вещественный
Временное хранение значения элемента массива при обмене
Примечание: потому что процедура сортировки массива – рекурсия, то переменные i, j, X – должны быть локальными.
Заключение
В процессе выполнения курсовой работы, я вызнал как представляются данные в ЦА, научился переводить числа из одной системы счисления в другую, научился представлять числа в машинном коде и делать над ними арифметические и логические операции. При исследовании способа контроля работы ЦА, я научился строить код Хемминга, также выявлять ошибки в данных, закодированных кодом Хемминга. При исследовании реализации метода численного способа «резвой сортировки», я узрел преимущество данного способа в отличии от остальных способов сортировки.
Таковым образом, при выполнении курсовой работы, я получил новейшие познания и способности для собственной проф деятель.
Перечень применяемых источников
1. Понаморев В.С., Красников В.В. Методические указания по курсу «Организация и функционирование ЭВМ и систем». Ч.1. Арифметические базы ЭВМ . ДГТУ, 1996.
2. веб-ресурс «Системы счисления: двоичная, восьмиричная, шестнадцатиричная»
HTTP://www.pascalstudy.narod.ru/tems/pas_5.html
3. Коштоев В.В., Кипиани К.К. Учебное пособие «Базы прикладной теории цифровых автоматов» Тбилиси, 1998.
4. веб-ресурс «Теоретические базы информатики. Коды Хемминга»
HTTP://de.uspu.ru/Informatics/Metodes/DPP/F/08/1/glavs/5/564.htm
5. веб-ресурс «Контроль по модулю арифметических операций в десятичной и двоичной СС»
HTTP://distance-onu.by.ru/metod/11.htm
6. Веб-ресурс «Глава 3. Выражения и Операции. Побитовые Операции Сдвига»
HTTP://pyramidin.narod.ru/jscript/coreguide15/expr.html
7. Turbo Pascal для школьников: Учеб. пособие.– 3-е доп.изд.– М.: деньги и статистика, 2002.–528 с.
приложение 1. Блок-схема метода
]]>