Курсовая работа: Динамічна пам'ять, принципи її організації і роботи
Таблиця 6. Двійкова послідовність символів імені з позиціями контрольних бітів.
| Позиція біта | 53 | 52 | 51 | 50 | 49 | 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 | 40 | 39 |
| Значення біта | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| Позиція біта | 38 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 |
| Значення біта | 0 | 1 | 1 | 0 | 1 | 1 | * | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| Позиція біта | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 |
| Значення біта | 0 | 1 | 0 | 1 | 1 | 1 | 0 | * | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Позиція біта | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|
||||||
| Значення біта | * | 0 | 0 | 0 | * | 1 | * | * |
|
||||||
* - позиції, де розміщуються контрольні біти
Контрольн біти резервуються цілою ступінню двійки. Оскільки номера контрольних біт становлять ступінь двійки, то з ростом розрядності кодового слова вони розташовуються все рідше і рідше. Контрольна сума формується шляхом використання операції XoR над кодами позицій ненульових бітів. Позиц ненульових бітів приведено в таблиці 7.
Таблиця 7. Позиції ненульових бітів
| Позиція | Код |
| 3 | 000011 |
| 10 | 001010 |
| 11 | 001011 |
| 14 | 001110 |
| 18 | 010010 |
| 19 | 010011 |
| 20 | 010100 |
| 22 | 010110 |
| 24 | 011000 |
| 27 | 011011 |
| 28 | 011100 |
| 33 | 100001 |
| 34 | 100010 |
| 36 | 100100 |
| 37 | 100101 |
| 39 | 100111 |
| Позиція | Код |
| 44 | 101100 |
| 45 | 101101 |
| 48 | 110000 |
| 49 | 110001 |
| 51 | 110011 |
| 52 | 110100 |
| 53 | 110101 |
Контрольна сума приведена в таблиці 8.
Таблиця 8. Контрольна сума.
| Позиція біта | 6 | 5 | 4 | 3 | 2 | 1 |
| онтр. Сума | 0 | 0 | 0 | 1 | 1 | 1 |
Таким чином приймач буде мати з розрахованими контрольними бітами (табл. 9).
Таблиця 9. Кодова послідовність на стороні приймача.
| Позиція біта | 53 | 52 | 51 | 50 | 49 | 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 | 40 | 39 |
| Значення біта | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| Позиція біта | 38 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 |
| Значення біта | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| Позиція біта | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 |
| Значення біта | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
Таблиця 9. Продовження
| Позиція біта | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| Значення біта | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Просумуємо кодову послідовність за допомогою операції XoR ще раз (табл. 10) і будемо мати нуль.
Таблиця 10. Контрольна сума кодової послідовності.
| Позиція біта | 6 | 5 | 4 | 3 | 2 | 1 |
| Контр. Сума | 0 | 0 | 0 | 0 | 0 | 0 |
2.3 Заміна на протилежне значення біту і можливість його виправлення
Змініть значення N-ного біту отриманої послідовності на протилежне та покажіть можливість його відновлення (де N – це ваш номер за журналом академічно групи). У доповнення до N-того біту також змініть на протилежне значення (35 N) біту. Чи є можливість тепер відновити інформацію? Наведіть пояснення.
Змінемо у кодовій послідовності біт (0→1) під номером (35 – N), де N = 3. Маємо змінений біт під номером 32 (табл. 11).
Таблиця 11. Кодова послідовність з помилкою.
| Позиція біта | 53 | 52 | 51 | 50 | 49 | 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 | 40 | 39 |
| Значення біта | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| Позиція біта | 38 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 |
| Значення біта | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| Позиція біта | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 |
| Значення біта | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Позиція біта | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|
||||||
| Значення біта | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
|
||||||
Просумуємо коди позицій ненульових бітів за допомогою операції XoR ще раз (табл. 12):
Таблиця 12. Контрольна сума позицій ненульових бітів з помилкою
| Позиція біта | 6 | 5 | 4 | 3 | 2 | 1 |
| Контр. Сума | 1 | 0 | 0 | 0 | 0 | 0 |
Контрольна сума дорівнює позиції біта, де сталася помилка. Для виправлення помилки приймачу треба інвертувати біт, номер якого вказаний у контрольній сумі (табл. 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.
