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

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.