.RU

Методические указания для выполнения курсовой работы по информатике для студентов специальностей 220100 Вычислительные машины, комплексы, системы и сети



Калининградский Государственный Технический Университет


Методические указания для выполнения курсовой работы по информатике для студентов специальностей 220100 – Вычислительные машины, комплексы, системы и сети 220200 – Автоматизированные системы обработки информации и управления


Калининград 2003 УДК 621.38 УТВЕРЖДЕНО Ректором Калининградского государственного технического университета
Автор – Топоркова О.М., к.т.н., доцент кафедры систем управления и вычислительной техники Калининградского государственного технического университета


Методические указания рассмотрены и одобрены кафедрой систем управления и вычислительной техники 24 декабря 2003 г, протокол № 4


Рецензент – кафедра систем управления и вычислительной техники Калининградского государственного технического университета


©Калининградский государственный технический университет, 2003 г.
Введение

Курсовая работа по информатике выполняется во втором семестре обучения, когда студенты изучили методы кодирования и измерения информации в дискретном сигнале.

В настоящих методических указаниях приведены задания по различным способам кодирования дискретного сигнала – по образцу, криптографическому, эффективному, помехозащитному. Решение этих задач связано с измерением информации, так что обе проблематики – кодирование и измерение – тесно переплетаются при решении практических задач и им посвящены первые две части заданий.

В третьей части приведено задание по моделированию действия арифметико-логического устройства, выполняющего сложение двух операндов в обратных кодах.

В четвертой части сформулированы задания по кодированию алгоритмов. Тематика задач связана с теми проблемами, которые решались в предыдущих частях настоящих методических указаний. Строго говоря, кодирование алгоритмов также относится к задаче кодирования дискретного сигнала, но тематика заданий, о которой упоминалось выше, регламентировала именно такое местоположение этих заданий.

По всем задачам даны подробные указания к их выполнению, оформленные в виде решений конкретных аналогичных задач. Приведены также правила оформления пояснительной записки.
^ Часть 1. Кодирование дискретного сигнала


1.1 Кодирование кодами по образцу


Задание 1. Прямые коды

Для алфавита А, используемого при формировании Вашей фамилии, имени, отчества (далее - исходного текста), построить прямые двоичные коды постоянной длины и закодировать ими исходный текст (т.е. фамилию, имя и отчество). Для простоты игнорировать регистр и пробелы между словами.
^ Указания по выполнению задания 1

Пусть фамилия, имя и отчество студента Петров Иван Васильевич. Тогда исходным текстом является текст

петровиванвасильевич, (1)

а алфавит А - это множество символов, {п, е, т, р, о, в, и, а, н, с, л, ь, ч}, т.е.

А = {п, е, т, р, о, в, и, а, н, с, л, ь, ч}. (2)

Для построения прямых кодов выполним следующую последовательность действий:

  1. множество А упорядочим по алфавиту (графа 1 табл.1),

  2. пронумеруем символы алфавита А, начиная с нуля (графа 2 табл.1),

  3. определим мощность N алфавита А (т.е. число символов алфавита):

N = 13 (3)

  1. используя комбинаторный подход к измерению информации, рассчитаем требуемый размер кода, достаточный для кодирования всех символов исходного алфавита А, по формуле:

l = [logh N] , (4)

где h – число символов, используемых для кодирования,

скобки [ ] означают округление результата до ближайшего большего целого числа.

Для нашего примера h = 2 (поскольку строится двоичный код), поэтому

l = [log2 13] = [3,7] = 4, (5)

  1. каждый номер символа представим четырехразрядным (как следует из шага 4) двоичным числом - получим код постоянной длины (графа 3 табл.1).


Таблица 1

Символ алфавита А

Номер по порядку

^ Код постоянной длины

1

2

3

а

0

0000

в

1

0001

е

2

0010

и

3

0011

л

4

0100

н

5

0101

о

6

0110

п

7

0111

р

8

1000

с

9

1001

т

10

1010

ч

11

1011

ь

12

1100


Кодирование исходного текста дает (для простоты закодируем отдельно фамилию, имя, отчество)1:

петров 0111 0010 1010 1000 0110 0001

иван 0011 0001 0000 0101 (6)

васильевич 0001 0000 1001 0011 0100 1100 0010 0001 0011 1011
^ Задание 2. Коды, учитывающие частоту символов

Построить для алфавита А, полученного в задании 1, двоичные коды, учитывающие частоту символов. Расчет частоты выполнить по исходному тексту. Закодировать полученным кодом исходный текст.

^ Указания по выполнению задания 2

Для построения требуемых кодов выполним следующую последовательность действий:

  1. для расчета частот символов из алфавита А (графа 1 табл. 2) определим число появлений mi каждого i-го символа алфавита А в исходном тексте (графа 2 табл. 2),



Таблица 2

Символ

алфавита А

Число

появлений mi

1

2

а

2

в

4

е

2

и

3

л

1

н

1

о

1

п

1

р

1

с

1

т

1

ч

1

ь

1




  1. для определения размера кода вновь используем формулу l = [logh N] при N = 13, h = 2. Получаем:

l = [logh 13] = [3,7] = 4, (7)

  1. используя комбинаторный подход к измерению информации, определим, сколько кодовых комбинаций можно получить из 4 двоичных разрядов, заполняя их нулями и единицами теми способами, которые показаны в графе 2 табл. 3. Чтобы решить эту задачу, установим, прежде всего, способ комбинирования символов двоичного алфавита (h = 2). Анализ кодов из табл. 1 показывает, что это перестановки с повторениями, для которых верно соотношение:


(ri)!

П(ri!)


Пп(h) = , (8)

где Пп(h) – число перестановок из h элементов с повторениями ri,

i – символ из множества символов, используемых для кодирования (у нас это множество {0,1}).

Теперь рассчитаем число кодовых комбинаций для каждого способа заполнения кодовых разрядов (графа 4 табл. 3).

Таблица 3

№ п/п

Способы заполнения кодовых разрядов

Обозначение в формуле (8)

^ Число кодовых комбинаций

1

2

3

4

1


1
все нули

r0 = 4, r1 = 0

(4+0)! 4!

4!*0! 4!

2


4
1 единица, 3 нуля

r0 = 3, r1 = 1

(1+3)! 4! 2*3*4

1!*3! 2*3 6

3


6
2 единицы, 2 нуля

r0 = 2, r1 = 2

(2+2)! 4! 2*3*4

2!*2! 2*2 4

4

3 единицы, 1 ноль

r0 = 1, r1 = 3

аналогично второму способу, т.е. 4

5

все единицы

r0 = 0, r1 = 4

аналогично первому способу, т.е. 1


Суммирование полученного числа кодовых комбинаций (1+4+6+4+1=16) показывает, что для кодирования символов исходного алфавита А с заданной мощностью N достаточно принятых способов заполнения разрядов кода, поскольку 16>(N=13),

  1. упорядочим список символов алфавита А по убыванию частоты. Получим табл. 4 (графы 1,2),

  2. назначим символам коды постоянной длины, число единиц в которых тем больше, чем меньше частота символа (графа 4 табл. 4).

Таблица 4

Символ

алфавита А

Число

появлений mi

Способы заполнения кодовых разрядов

Код

^ Число кодовых комбинаций2

1

2

3

4

5

в

4

все нули

0000

1

и

3

1 единица, 3 нуля

0001

4

а

2

1 единица, 3 нуля

0010

е

2

1 единица, 3 нуля

0100

л

1

1 единица, 3 нуля

1000

н

1

2 единицы, 2 нуля

1010

6

о

1

2 единицы, 2 нуля

1001

п

1

2 единицы, 2 нуля

0110

р

1

2 единицы, 2 нуля

0101

с

1

2 единицы, 2 нуля

0011

т

1

2 единицы, 2 нуля

1100

ч

1

3 единицы, 1 ноль

1011

2

ь

1

3 единицы, 1 ноль

1101


Кодирование исходного текста полученным кодом дает результат (отдельно закодированы фамилия, имя и отчество):

петров 0110 0100 1100 0101 1001 0000

иван 0001 0000 0010 1010 (9)

васильевич 0000 0010 0011 0001 1000 1101 0100 0000 0001 1011


^ Задание 3. Коды Грея

Для символов алфавита А (из задания 1) построить код Грея. Закодировать полученным кодом исходный текст.
Указания к выполнению задания 3

Для построения кода Грея выполним следующие шаги:

  1. исходя из мощности множества А, определим размер nxm таблицы для построения кода Грея, где n – число строк, m – число столбцов таблицы. Для этого будем последовательно наращивать число столбцов и число строк, начиная с одной строки и одного столбца, каждый раз проверяя, не достигнут ли требуемый размер таблицы. При этом схема наращивания числа строк и столбцов будет определяться следующим образом: число столбцов на каждом шаге итерации равно или на 1 превышает число строк (табл. 5).

Таблица 5

^ Номер шага

Число столбцов m

Число строк n

Размер таблицы nxm

1

2

3

4

1

1

1

1

2

2

1

2

3

2

2

4

4

3

2

6

5

3

3

9

6

4

3

12

7

4

4

16 > 13


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

  1. строки и столбцы таблицы пронумеруем двоичными числами из множества {00, 01, 10, 11}, элементы которого сами являются кодами Грея (затушеванные ячейки табл. 6),

Таблица 6




00

01

11

10

00

а

в

е

и

01

п

о

н

л

11

р

с

т

ч

10










ь




  1. разместим в ячейках таблицы упорядоченные по алфавиту символы исходного множества (см. графу 1 табл.1) в направлении, указанном стрелками в табл.6,

  2. для формирования кода Грея по каждому символу объединим номера строки и столбца ячейки, в которой находится символ. Получим графу 2 табл. 7.

Таблица 7

Символ алфавита А

Код Грея

1

2

а

0000

в

0001

е

0011

и

0010

л

0110

н

0111

о

0101

п

0100

р

1100

с

1101

т

1111

ч

1110

ь

1010


Кодирование исходного текста полученным кодом дает результат:

петров 0100 0011 1111 1100 0101 0001

иван 0010 0001 0000 0111 (10)

васильевич 0001 0000 1101 0010 0110 1010 0011 0001 0010 1110

metodicheskie-ukazaniya-k-kursovoj-rabote-po-discipline-stranica-7.html
metodicheskie-ukazaniya-k-kursovoj-rabote-po-zemledeliyu-na-temu-proektirovanie-sevooborotov.html
metodicheskie-ukazaniya-k-kursovoj-rabote-sankt-peterburg.html
metodicheskie-ukazaniya-k-kursovoj-rabote.html
metodicheskie-ukazaniya-k-kursovomu-i-diplomnomu-proektirovaniyu-moskva-2007.html
metodicheskie-ukazaniya-k-kursovomu-proektirovaniyu-informacionnie-tehnologii-upravleniya-nauchnimi-kollektivami-i-analiza-rinka-truda.html
  • uchebnik.bystrickaya.ru/v-osnove-kommunisticheskoj-nravstvennosti-lezhit-borba-za-uskorenie-i-zavershenie-kommunizma.html
  • zadachi.bystrickaya.ru/upravlenie-kachestvom-i-konkurentosposobnost-produkcii.html
  • essay.bystrickaya.ru/deti-volki-deti-pandi.html
  • klass.bystrickaya.ru/analiz-raboti-mo-fito-2009-2010gg-mo-fito-v-tekushem-god.html
  • uchit.bystrickaya.ru/sutra-o-cvetke-lotosa-chudesnoj-dharmi-stranica-17.html
  • institute.bystrickaya.ru/filosofiya-etika-byulleten-novoj-literaturi-postupivshej-v-fond-nauchnoj-biblioteki-chgpu.html
  • desk.bystrickaya.ru/ochagovij-tuberkulez-infiltrativnij-tuberkulez.html
  • laboratornaya.bystrickaya.ru/rabota-administrativnogo-soveta-programma-razvitiya-srednej-obsheobrazovatelnoj-shkoli-2-na-2011-2016-god-shkola.html
  • shpora.bystrickaya.ru/yu-n-bagrova-sozdanie-tehnoparka-v-sfere-visokih-tehnologij.html
  • predmet.bystrickaya.ru/resheni-e-stranica-14.html
  • uchenik.bystrickaya.ru/federalnie-normi-i-pravila-v-oblasti-ispolzovaniya-atomnoj-energii-stranica-4.html
  • turn.bystrickaya.ru/orinbor-aza-avtonomiyasini-tish-astanasini-tarihina-totalu.html
  • bukva.bystrickaya.ru/rukovodstvo-po-ekspluatacii-556-088-re-stranica-5.html
  • knigi.bystrickaya.ru/repertuarnij-plan-s-1-po-31-marta-2012-goda-teatralnie-uroki-spektakli.html
  • letter.bystrickaya.ru/metodicheskij-centr-suo-stranica-8.html
  • predmet.bystrickaya.ru/socialnij-pasport-doklad-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-srednyaya-obsheobrazovatelnaya-shkola-3.html
  • zanyatie.bystrickaya.ru/shukshin-v-m-mir-geroev-shukshina.html
  • reading.bystrickaya.ru/krug-3-boj-o-4-temi-krug-1-boj-a-4-temi.html
  • gramota.bystrickaya.ru/vserossijskaya-ochno-zaochnaya-konferenciya-aktualnie-problemi-sovremennoj-pedagogiki-i-psihologii-.html
  • institut.bystrickaya.ru/tezisnij-plan-vvedenie-istoricheskie-usloviya-predprinimatelstva-v-rossii-usloviya.html
  • textbook.bystrickaya.ru/kartochka-na-vopros-9-o-e-shumilova.html
  • pisat.bystrickaya.ru/trifon-neputyovij-stranica-4.html
  • literatura.bystrickaya.ru/spisok-novoj-literaturi-postupivshej-v-biblioteku-stranica-5.html
  • upbringing.bystrickaya.ru/kratkaya-harakteristika-tovara-i-kolichestvo-tovara-sm-v-konkursnoj-dokumentacii-v-prilozhenii-kratkaya-harakteristika-i-kolichestvo-tovara.html
  • turn.bystrickaya.ru/opisanie-zagolovka-tekst-dokumenta.html
  • upbringing.bystrickaya.ru/kompleks-standartov-na-avtomatizirovannie-sistemi-avtomatizirovannie-sistemi.html
  • laboratory.bystrickaya.ru/valyutnij-kontrol-za-postupleniem-v-rossijskuyu-federaciyu-valyutnoj-viruchki-ot-eksporta-tovarov-chast-5.html
  • occupation.bystrickaya.ru/obzhd-ekologiya-sh-biologiya-geografiya-stranica-2.html
  • desk.bystrickaya.ru/polyarnaya-pravda-murmansk-188-26122008-etot-ogon-nikogda-ne-pogasnet.html
  • lesson.bystrickaya.ru/pravovoj-poryadok-metodi-i-instrumenti-regulirovaniya-denezhnoj-massi-i-denezhnogo-obrasheniya.html
  • uchit.bystrickaya.ru/tehnologicheskaya-instrukciya-plazmennaya-svarka-ustanovit-tok-4-ili-5-a-i-napryazhenie-120-140-v-vipolnit.html
  • university.bystrickaya.ru/galimullin-foat-bibliograficheskij-ukazatel-knig-postupivshih-v-biblioteku.html
  • znanie.bystrickaya.ru/akt-selo-celinnij-abzelilovskogo-rajona-respublika-bashkortostan-1-obshie-polozheniya-dokumenti-udostoveryayushie.html
  • universitet.bystrickaya.ru/tema-i-predlagaemie-vibori-praktikum-po-psihodiagnostike-deviantnogo-povedeniya-u-trudnih-podrostkov.html
  • shkola.bystrickaya.ru/ocenka-inzhenerno-geologicheskih-i-gidrogeologicheskih-uslovij-rajona-stroitelstva.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.