.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
  • predmet.bystrickaya.ru/sabati-masati-oushilardi-bauirzhan-momishlini-mr-turali-tsnk-beru.html
  • control.bystrickaya.ru/epohi-zhizni-kniga-adresovana-shirokomu-krugu-sereznih-chitatelej-v-tom-chisle-starshim-shkolnikam-studentam-i-prepodavatelyam.html
  • thescience.bystrickaya.ru/kak-otkrit-radost-tvorcheskogo-mishleniya-maksvell-dzhon-s.html
  • spur.bystrickaya.ru/konstrukciya-ortotropnoj-pliti-proezzhej-chasti-snip-05-03-84-1991-mosti-i-trubi-chast-2.html
  • institute.bystrickaya.ru/glava-1-teoreticheskie-podhodi-k-probleme-interpretacii-hudozhestvennogo-teksta.html
  • books.bystrickaya.ru/enciklopediya-populyarnoj-muziki-kirilla-i-mefodiya-2004-annotirovannij-ukazatel-diskov-i-videokasset-imeyushihsya-v-mou-oosh-26.html
  • portfolio.bystrickaya.ru/organizaciya-upravlencheskogo-truda.html
  • paragraf.bystrickaya.ru/zadacha-obespechenie-dostojnogo-urovnya-vzaimodejstviya-s-zayavitelyami-11-stranica-3.html
  • kontrolnaya.bystrickaya.ru/razbros-oblomkov-razbivshegosya-an-12-na-kolime-sostavlyaet-5-km-poiskovie-raboti-budut-prodolzheni-11-avgusta-mchs-informacionnoe-agentstvo-itar-tass-10082011.html
  • lektsiya.bystrickaya.ru/prilozhenie-3-s-otchet-po-specialnosti-080502-ekonomika-i-upravlenie-na-predpriyatiyah-gorodskoe-hozyajstvo-fem-tgasu.html
  • credit.bystrickaya.ru/os-ardagerler-men-mgedekterne-zhne-teestrlgen-azamattara-zhest-70-zhildiina-oraj-saltanatti-merekelk-bankett-jimdastiru-zhnemerekelk-dalali-botasin.html
  • learn.bystrickaya.ru/g-rasskazovo-tambovskoj-oblasti-vneklassnogo-meropriyatiya.html
  • learn.bystrickaya.ru/gerakl.html
  • shpargalka.bystrickaya.ru/urok-po-teme-shkolnie-predmeti.html
  • institut.bystrickaya.ru/teoriya-muziki-muzikalnoe-iskusstvo-estradi-dorogie-druzya.html
  • control.bystrickaya.ru/doklad-pravoprimeneniya-federalnogo-zakona-rf-ot-27-12-1991goda-2124-1-o-sredstvah-massovoj-informacii-aprel-2012-god.html
  • studies.bystrickaya.ru/analiz-hozyajstvennoj-deyatelnosti-i-ispolzovaniya-mtp-v-fgup-uoh-iyulskoe-votkinskogo-rajona-ur.html
  • reading.bystrickaya.ru/kontrolnaya-rabota-dolzhna-bit-vipolnena-na-10-15-stranicah-mashinopisnogo-teksta-i-sostoyat-iz-razdelov-osnovnaya-chast-vivodi-spisok-literaturi.html
  • upbringing.bystrickaya.ru/krang-chzhisun-kalendar-znamenatelnih-i-pamyatnih-dat-po-buryatii.html
  • exchangerate.bystrickaya.ru/aleksandr-i-chast-3.html
  • occupation.bystrickaya.ru/metodicheskie-ukazaniya-po-podgotovke-i-zashite-vipusknoj-kvalifikacionnoj-raboti-dlya-studentov-vseh-form-obucheniya-specialnost-080502-ekonomika-i-upravlenie-stranica-2.html
  • student.bystrickaya.ru/02042010novaya-nedelya-itogi-naberezhnie-chelni-bivshaya-chelninskaya-nedelyavstrechaem-pashu.html
  • ekzamen.bystrickaya.ru/speckurs-psihologiya-garmonizacii-lichnosti-dlya-studentov-vechernego-otdeleniya-moskva-2009.html
  • teacher.bystrickaya.ru/genrih-byoll-glazami-klouna-stranica-19.html
  • zanyatie.bystrickaya.ru/pisma-yunreriha-k-ryarudzitisu-vospominaniya-o-yu-n-rerihe.html
  • shkola.bystrickaya.ru/proizvodstvo-v-arbitrazhnom-sude-rf-chast-18.html
  • institute.bystrickaya.ru/fizicheskaya-kultura-obespechenie-obrazovatelnogo-processa-uchebnoj-i-uchebno-metodicheskoj-literaturoj-n-pp.html
  • prepodavatel.bystrickaya.ru/tema-17-ponyatie-i-sushnost-gosudarstva-osnovnie-problemi-sovremennogo-ponimaniya-gosudarstva.html
  • lektsiya.bystrickaya.ru/prilozhenie-b-obosnovanie-i-razrabotka-effektivnih-metodov-lekarstvennogo-obespecheniya-na-urovne-visokospecializirovannoj.html
  • institut.bystrickaya.ru/teoriya-statistiki-2.html
  • occupation.bystrickaya.ru/ndustralzacya-ukrani-ekzamenacionnie-voprosi-pervobitnij-stroj-v-ukraine-tripolsnaya-kultura.html
  • otsenki.bystrickaya.ru/reglament-raboti-administracii-rajona.html
  • grade.bystrickaya.ru/mizansceni-tolpi-igra-v-associacii-14-zritelnij-i-zvukovoj-ryad-23.html
  • student.bystrickaya.ru/35-vospitatelnaya-rabota-publichnij-otchet-o-rezultatah-deyatelnosti-gbou-spo-pk5-za-2010-2011-uchebnij-god.html
  • teacher.bystrickaya.ru/glava-devetzavrshane-v-dancho-gospodinov-prevod-2003.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.