Динамічна пам'ять, принципи її організації і роботи

Подання чисел у двійковому коді.

Подання чисел у пам'яті комп'ютера має специфічну особливість, пов'язану з тим, що в пам'яті комп'ютера вони повинні розташовуватися в байтах - мінімальних по розмірі адресуємих (тобто до них можливе обіг) комірках пам'яті. Очевидно, адресою числа варто вважати адреса першого байта. У байті може втримуватися довільний код з восьми двійкових розрядів, і завдання подання полягає в тім, щоб указати правила, як в одному або декількох байтах записати число.

Дійсне число багатообразне у своїх "споживчих властивостях". Числа можуть бути цілі точні, дробові точні, раціональні, ірраціональні, дробові наближені, числа можуть бути позитивними й негативними. Числа можуть бути "карликами", наприклад, маса атома, "гігантами", наприклад, маса Землі, реальними, наприклад, кількість студентів у групі, вік, ріст. І кожне з перерахованих чисел зажадає для оптимального подання в пам'яті своя кількість байтів.

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

Цілі числа. Цілі позитивні числа від 0 до 255 можна представити безпосередньо у двійковій системі числення (двійковому коді). Такі числа будуть займати один байт у пам'яті комп'ютера (табл. 3).

Таблиця 3. Двійковій код цілих чисел.

У такій формі подання легко реалізується на комп'ютерах двійкова арифметика.

Якщо потрібні й негативні числа, то знак числа може бути закодований окремим битому, звичайно це старший біт; нуль інтерпретується як плюс, одиниця як мінус. У такому випадку одним байтом може бути закодовані цілі числа в інтервалі від -127 до +127, причому двійкова арифметика буде трохи ускладнена, тому що в цьому випадку існують два коди, що зображують число нуль 0000 0000 й 1000 0000, і в комп'ютерах на апаратному рівні це буде потрібно передбачити. Розглянутий спосіб подання цілих чисел називається прямим кодом. Положення з негативними числами трохи спрощується, якщо використати, так званий, додатковий код. У додатковому коді позитивні числа збігаються з позитивними числами в прямому коді, негативні ж числа виходять у результаті вирахування з 1 0000 0000 відповідного позитивного числа. Наприклад, число -3 одержить код:

_ 1 0000 0000

0000 0011

1111 1101

У додатковому коді добре реалізується арифметика, тому що кожен наступний код виходить із попереднім додатком одиниці з точністю до біта в дев'ятому розряді. Наприклад

5-3 = 5 + (-3)

0000 0101

1111 1101

1 0000 0010, тобто, відкидаючи підкреслений старший розряд, одержимо 2.

Аналогічно цілі числа від 0 так 65536 і цілі числа від -32768 до 32767 у двійковій (шістнадцатеричної) системі числення представляються у двобайтових осередках. Існують подання цілих чисел й у чотирьобайтових осередках.

Дійсні числа. Дійсні числа в математику представляються кінцевими або нескінченними дробами, тобто точність подання чисел не обмежена. Однак у комп'ютерах числа зберігаються в регістрах і комірках пам'яті, які являють собою послідовність байтів з обмеженою кількістю розрядів. Отже, нескінченні або дуже довгі числа усікаються до деякої довжини й у комп'ютерному поданні виступають як наближені. У більшості систем програмування в написанні дійсних чисел ціла й дробова частини розділяються не комі, а крапкою.

Для подання дійсних чисел, як дуже маленьких, так і дуже більших, зручно використати форму запису чисел у вигляді добутку у формулі 3.

X = m * qp

де m - мантиса числа;

q - підстава системи числення;

р - ціле число, називане порядком.

Такий спосіб запису чисел називається поданням числа із плаваючою крапкою.

Тобто число 4235,25 може бути записане в одному з видів:

4235,25 = 423,525 - 101 = 42,3525 - 102 = 4,23525 - 103 = 0,423525 - 104.

Очевидно, таке подання не однозначно. Якщо мантиса 1 / q < |m| < q (0,1 < |m| < 1 для десяткової системи числення), то подання числа стає однозначним, а така форма називається нормалізованої. Якщо "плаваюча" крапка розташована в мантисі перед першою значущою цифрою, то при фіксованій кількості розрядів, відведених під мантису, забезпечується запис максимальної кількості значущих цифр числа, тобто максимальна точність.

Дійсні числа в комп'ютерах різних типів записуються по-різному, проте існує кілька міжнародних стандартних форматів, що розрізняються по точності, але мають однакову структуру. Розглянемо на прикладі числа, що займає 4 байти (мал. 9).

Малюнок 9. Формат числа, що займає 4 байти

Перший біт двійкового подання використається для кодування знака мантиси. Наступна група біт кодує порядок числа, а біти, що залишилися, кодують абсолютну величину мантиси. Довжини порядку й мантиси фіксуються.

Порядок числа може бути як позитивним, так і негативним. Щоб відбити це у двійковій формі, величина порядку представляється у вигляді суми щирого порядку й константи, рівній абсолютній величині максимального по модулі негативного порядку, називаної зсувом. Наприклад, якщо порядок може приймати значення від -128 до 127 (8 біт), тоді, вибравши як змішання 128, можна представити діапазон значень порядку від 0 (-128+128, порядок + зсув) до 255 (127+128),

Тому що мантиса нормалізованого числа завжди починається з нуля, деякі схеми подання його лише мають на увазі, використовуючи зайвий розряд для підвищення точності подання мантиси.

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

Чим більше розрядів приділяється під запис мантиси, тим вище точність подання числа. Чим більше розрядів займає порядок, тим ширше діапазон від найменшого відмінного від нуля числа до найбільшого числа, представимого в комп'ютері при заданому форматі.

Речовинні числа в пам'яті комп'ютера, залежно від необхідної точності (кількості розрядів мантиси) і діапазону значень (кількості розрядів порядку), займають від чотирьох до десяти байтів. Наприклад, чотирьобайтове речовинне число має 23 розряду мантиси (що відповідає точності числа 7-8 десяткових знаків) і 8 розрядів порядку (забезпечуючи діапазон значень 10±38). Якщо речовинне число займає десять байтів, то мантисі приділяється 65 розрядів, а порядку - 14 розрядів. Це забезпечує точність 19-20 десяткових знаків мантиси й діапазон значень 10±4931.

Поняття типу даних. Як уже говорилося, мінімально адресуемою одиницею пам'яті є байт, але подання числа вимагає більшого обсягу. Очевидно, такі числа займуть групу байт, а адресою числа буде адреса першого байта групи. Отже, довільно взятий з пам'яті байт нічого нам не скаже про те, частиною якого інформаційного об'єкта він є - цілого числа, числа із плаваючої коми або команди. Резюмуючи вищесказане, можна зробити висновок, що крім завдання подання даних у двійковому коді, паралельно вирішується зворотне завдання - завдання інтерпретації кодів, тобто як з кодів відновити первісні дані.

2 ПРАКТИЧНА ЧАСТИНА

2.1 Переклад символів імені у послідовність цифр 16-річної системи числення

Використовуючи таблицю ASCII кодів перекладіть своє прізвище або ім'я (але менш чим 5 літер) у послідовність цифр 16-річної системи числення, а потім у послідовність двійкових біт (табл. 4).

Таблиця 4. Переклад літер у 16- та 2-річну СЧ

2.2 Доповнення послідовності двійковими бітами коду Хемінга

Користуючись викладеним теоретичним матеріалом доповніть послідовність двійкових біт бітами коду Хемінга.

Користуючись інформацією, яка викладена у методичних вказівках що до виконання курсової роботи з дисципліни "АРХІТЕКТУРА КОМП'ЮТЕРІВ" доповнюємо послідовність двійковими бітами коду Хемінга табл. 5.

Таблиця 5. Двійкова послідовність символів імені

Доповнюємо кодову послідовність бітами коду Хемінга. Результат у табл. 6.

Таблиця 6. Двійкова послідовність символів імені з позиціями контрольних бітів.

* - позиції, де розміщуються контрольні біти

Контрольні біти резервуються цілою ступінню двійки. Оскільки номера контрольних біт становлять ступінь двійки, то з ростом розрядності кодового слова вони розташовуються все рідше і рідше. Контрольна сума формується шляхом використання операції XoR над кодами позицій ненульових бітів. Позиції ненульових бітів приведено в таблиці 7.

Таблиця 7. Позиції ненульових бітів

Контрольна сума приведена в таблиці 8.

Таблиця 8. Контрольна сума.

Таким чином приймач буде мати з розрахованими контрольними бітами (табл. 9).

Таблиця 9. Кодова послідовність на стороні приймача.

Таблиця 9. Продовження

Просумуємо кодову послідовність за допомогою операції XoR ще раз (табл. 10) і будемо мати нуль.

Таблиця 10. Контрольна сума кодової послідовності.

2.3 Заміна на протилежне значення біту і можливість його виправлення

Змініть значення N-ного біту отриманої послідовності на протилежне та покажіть можливість його відновлення (де N - це ваш номер за журналом академічної групи). У доповнення до N-того біту також змініть на протилежне значення (35 - N) біту. Чи є можливість тепер відновити інформацію? Наведіть пояснення.

Змінемо у кодовій послідовності біт (0>1) під номером (35 - N), де N = 3. Маємо змінений біт під номером 32 (табл. 11).

Таблиця 11. Кодова послідовність з помилкою.

Просумуємо коди позицій ненульових бітів за допомогою операції XoR ще раз (табл. 12):

Таблиця 12. Контрольна сума позицій ненульових бітів з помилкою

Контрольна сума дорівнює позиції біта, де сталася помилка. Для виправлення помилки приймачу треба інвертувати біт, номер якого вказаний у контрольній сумі (табл. 12).

2.4 Написання програми кодування слова

Написати програму, яка дозволяє кодувати слова довжиною до 10 літер за схемою «ASCII-код > двійковий код > код Хемінга».

Збудуємо блок-схему алгоритму функціонування програми (мал. 10.).

Користуючись блок-схемою та алгоритмом для побудови коду Хемінга напишемо програму на алгоритмічному язиці Paskal (додаток А).

Малюнок 10. Блок-схема алгоритму програми

ВИСНОВКИ

У результаті виконаної курсової роботи було досягнуто наступних результатів:

1. У першому розділі було розглянуто питання та проблеми, пов'язані з динамічною оперативною пам'яттю (Dynamic RAM -- DRAM), яка використовується в більшості систем оперативної пам'яті сучасних персональних комп'ютерів. Основна перевага пам'яті цього типу полягає в тому, що її комірки упаковані дуже щільно, тобто в невелику мікросхему можна упакувати багато бітів, а значить, на їх основі можна побудувати пам'ять великої ємкості. Елементи пам'яті в мікросхемі DRAM -- це крихітні конденсатори, які утримують заряди. Саме так (наявністю або відсутністю зарядів) і кодуються біти. Проблеми, пов'язані з пам'яттю цього типа, викликані тим, що вона динамічна, тобто повинна постійно регенеруватися, оскільки інакше електричні заряди в конденсаторах пам'яті «стікатимуть» і дані будуть втрачені.

2. Термін інформація - латинського походження (informatio), означає роз'яснення, повідомлення, поінформованість. Інформація є одним з найцінніших ресурсів суспільства поряд з такими природними багатствами як нафта, газ та інші. Отже, методи та засоби переробки інформації як і переробки матеріальних ресурсів, можна визначити як технологію.

Одиницею інформації в комп'ютері є один біт. Один біт може приймати лише одне з двох можливих значень, а тому не може бути використаний для представлення великої кількості інформації. Числові величини в комп'ютері (в тому числі коди символів) представлені в двійковій позиційній системі числення (системі числення з основою 2).

Це означає, що для запису будь-якого числа можуть використовуватися лише дві цифри 0 та 1. Таким чином уся інформація в ЕОМ представлена у виді послідовності 0 та 1.

3. В елементах пам'яті, виготовлюваних у вигляді напівпровідникових ВІС, а також в процесорах підвищеної надійності використовується оперативний апаратний контроль за допомогою кодів Хемінга. У практичній частині курсової роботи були реалізовані питання, що до алгоритмів кодування Хемінга довільної послідовності кодів, та виправлення помилок у цій послідовності.

4. При роботі з кодовими послідовностями використовувались методи і принципи, які дозволяли знаходити , виправляти, корегувати та визначати помилки у послідовностях кодів Хемінга.

5. Також була написана програма, яка дозволяє кодувати слова довжиною до 10 літер за схемою «ASCII-код > двійковий код > код Хемінга».

ЛІТЕРАТУРНІ ДЖЕРЕЛА

[1] Т Кохонен. Ассоциативные запоминающие устройства. Пер. с англ. Мир, М. 384 с. (1982).

[2] Л.П.Ланцов, Л.Н.Зворыкин, И.Ф.Осипов. Цифровые устройства на комплементарных МОПинтегральных микросхемах. Радио и связь, М. 272 с. 1983.

[3] О.Н. Лебедев. Применение микросхем памяти в электронных устройствах. Радио и связь, М. 216 с. (1994).

[4] О.Н. Лебедев, А-Й.К. Марцинкчвичус, Э-Ф.К. Баганскис. Микросхемы памяти. ЦАП и АЦП. КУбК, М. 384 с. (1996).

[5] О.Н. Лебедев, А.И. Мирошниченко, В.А. Телец. Изделия электронной техники. Цифровые микросхемы.Микросхемы памяти. Микросхемы ЦАП И АЦП. Радио и связь, М. 248 с. (1994).

[6] А.Х.Мурсаев, Е.П.Угрюмов. Структуры и схемотехника современных нтегральных полупроводниковых запоминающих устройств.ГЭТУ,СПб.69 с. 1997.

[7] D. Kresta, T. Johnson. High-Level Design Methodology Comes Into Its Own // Electronic Design, 12, pp. 57-60 (1999).

[8] Y. Oshima, B. Sheu, S. Jen. High-Speed Memory Architectures for Multimedia Applications // IEEE Circuits & Devices, 1(13), pp. 8-13 (1997).

[9] Y. Takai, M. Nagase, M. Kitamura. 250 Mbyte/s Synchronous DRAM Using a 3-Stage-Pipelined Architecture //IEEE Journal of Solid State Circuits, 4(29), pp. 426-429 (1994).

[10] S. Novosiadlyi, M. Mykhalchuk, D. Fedasyuk. Basic Principles and Elements of highly effective System Technology of VLSI Microelectronics // Proceedings of the 6-th International Conference“ Mixed Design of Integrated Circuits and Sistems MIXDES'-99“, Krakov, Poland, pp. 267-270 (1999).

[11] Таненбаум Э. Архитектура компьютера. - СПб.: Питер, 2002. - 704 с.

[12] Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986. - 576 с.

ДОДАТОК А

Текст програми

Program Heming;

uses Crt;

const APower2: array[0..7] of Integer = (1, 2, 4, 8, 16, 32, 64, 128);

{ Массив степеней 2-ки}

var

ASymbol: array [1..8] of ShortInt; { Массив для хранения бинарного кода символа}

ABinCod: array [1..80] of ShortInt; { Массив для хранения бинарного кода слова}

AContrSum: array [0..7] of Integer; { Массив для хранения контрольных сумм}

AHemCod: array [1..88] of ShortInt; { Массив для хранения бинарного кода}

{ дополненного контрольными битами}

NBinCod, NHemCod: Integer; { Количество битов бинарного и кодированного} { видов слова соответственно}

i, j, k, n, NCur: Integer; { вспомогательные переменные}

NContr: Integer; { счетчик контрольных битов}

Slovo, ASCIICod, BinCod, HemCod: String;

procedure DecToBin(n: Integer); { процедура перевода десятичного числа в массив битов}

var i: Integer;

begin

for i:=1 to 8 do ASymbol[i]:=0;

i:=8;

while n>1 do

begin

ASymbol[i]:=n mod 2;

n:=n div 2;

dec(i);

end;

ASymbol[i]:=n;

end;

function CheckCod: Integer; { Процедура проверки кода на наличие повреждения}

var i, j, n, Res:Integer; { возвращаемое значение - номер поврежденного бита}

begin { или 0, если код не поврежден}

for i:=0 to 7 do { определение количества контрольных битов}

if NHemCod<APower2[i] then

begin

NContr:=i;

Break;

end;

for i:=0 to NContr-1 do AContrSum[i]:=0; { обнуление контрольных сумм}

NCur:=0;

for i:=1 to NHemCod do

if i=APower2[NCur] then inc(NCur) { если номер бита - степень 2-ки, пропускаем его}

else if AHemCod[i]>0 then { иначе если бит - 1-ца прибавляем 1 к каждому}

begin { контрольному биту, контролирующий i-й, для чего}

n:=i; { раскладываем i по степеням двойки}

for j:=NContr-1 downto 0 do

if n>=APower2[j] then

begin

inc(AContrSum[j]);

n:=n-APower2[j];

end;

end;

Res:=0; { определение номера поврежденного бита по несовпавшим}

for i:=0 to NContr-1 do { контрольным суммам}

if (AContrSum[i] mod 2)<>AHemCod[APower2[i]] then Res:=Res+APower2[i];

CheckCod:=Res;

end;

Begin

ClrScr;

Writeln(' ПРОГРАММА ДЛЯ ПЕРЕВОДА СЛОВ В КОД ХЕМИНГА');

Write('Введите слово для кодирования (максимум - 10 букв):');

Readln(Slovo);

if Length(Slovo)<1 then { проверка наличия введенных символов}

begin

Writeln('Нужно ввести слово');

Halt;

end;

if Length(Slovo)>10 then { проверка длины слова}

begin

Writeln('Длина слова - не более 10 символов');

Halt;

end;

BinCod:='';

HemCod:='';

Write('ASCII-код слова: ');

for i:=1 to Length(Slovo) do

begin

Write(Ord(Slovo[i]), ' ');

{ перевод символа в ASCII-код}

DecToBin(Ord(Slovo[i])); { перевод символа в бинарный код}

for j:=1 to 8 do

ABinCod[(i-1)*8+j]:=ASymbol[j];

{ добавление бинарного кода символа к слову}

end;

Writeln;

NBinCod:=Length(Slovo)*8;

while ABinCod[1]=0 do { удаление лидирующих нулей в двоичном виде слова}

begin

for i:=1 to NBinCod-1 do ABinCod[i]:=ABinCod[i+1];

dec(NBinCod);

end;

Write('Бинарный код слова: ');

for i:=1 to NBinCod do Write(ABinCod[i]);

Writeln;

for i:=0 to 7 do AContrSum[i]:=0; { обнуление массивов}

for i:=1 to 88 do AHemCod[i]:=0;

i:=NBinCod;

j:=1;

NContr:=0;

while i>0 do { кодируем слово начиная с конца}

begin

if j=APower2[NContr] then inc(NContr) { если номер бита - степень 2-ки резервируем его для контрольного бита}

else if ABinCod[i]>0 then { записываем информационный бит, если он - 1-ца}

begin

AHemCod[j]:=1;

n:=j;

k:=0;

while n>1 do { увеличение контрольных сумм битов, контролирующих

j-й символ кодированной строки}

begin

if Odd(n) then inc(AContrSum[k]);

n:=n div 2;

inc(k);

end;

inc(AContrSum[k]);

dec(i);

end

else dec(i); { если инф. бит 0 - переходим на следующий без увеличения

контрольных сумм}

inc(j);

end;

NHemCod:=j-1; { длина кодированной последовательности}

for i:=0 to NContr-1 do if Odd(AContrSum[i]) then AHemCod[APower2[i]]:=1;

{ расчет значений контрольных битов по контрольным суммам}

{ вывод кодированной последовательности}

Write('Код Хеминга слова: ');

for i:=NHemCod downto 1 do Write(AHemCod[i]);

Writeln;

Writeln;

Writeln('Изменяем 32-й бит в коде Хеминга');

if AHemCod[32]=1 then AHemCod[32]:=0

else AHemCod[32]:=1;

Write('Поврежденный код Хеминга: ');

for i:=NHemCod downto 1 do Write(AHemCod[i]);

Writeln;

n:=CheckCod; { определение поврежденного бита (если таковой есть)}

if n>NHemCod then { количество повреждений явно больше 1}

Writeln('По-видимому ошибок больше одной, декодирование невозможно')

else if n>0 then { вывод исправленного кода и сообщения об исправлении}

begin

if AHemCod[n]=0 then AHemCod[n]:=1 else AHemCod[n]:=0;

Writeln('Исправлен ', n, '-й бит');

Write('Исправленный код Хеминга: ');

for i:=NHemCod downto 1 do Write(AHemCod[i]);

Writeln;

end

else Writeln('Код верен. Исправления не требуется.');

Writeln;

End.

Страницы: 1, 2