.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
  • student.bystrickaya.ru/2-predmet-dogovora-sroki-ispolneniya-obyazatelstv-poryadok-oplati-11-stranica-11.html
  • prepodavatel.bystrickaya.ru/terminologicheskuyu-strogost-tehnicheskogo-znaniya-i-specificheskie-metodi-ego-fiksacii.html
  • books.bystrickaya.ru/data-formirovaniya-01-06-2010-reestr-vidannih-licenzij-na-roznichnuyu-prodazhu-alkogolnoj-produkcii-stranica-6.html
  • institute.bystrickaya.ru/finansovaya-akademiya-pri-pravitelstve-rossijskoj-federacii.html
  • lecture.bystrickaya.ru/57-novie-tehnologii-upravleniya-a-s-bolshakov-menedzhment.html
  • studies.bystrickaya.ru/istoriya-i-znachenie-burovzrivnih-rabot.html
  • books.bystrickaya.ru/detskij-konkurs-fotografij-i-rasskazov-luchshij-papin-vihodnoj-dalee-konkurs-provoditsya-v-ramkah-programmi-profilaktiki-narushenij-tehniki-bezopasnosti-na-predpriyatiyah-gruppi-kompanij-norilskij-nikel.html
  • kolledzh.bystrickaya.ru/annotaciya-primernoj-programmi-uchebnoj-disciplini-vichislitelnie-sistemi-seti-i-telekommunikacii-celi-i-zadachi-disciplini.html
  • otsenki.bystrickaya.ru/specifika-i-perspektivi-razvitiya-malogo-predprinimatelstva-v-murmanskoj-oblasti.html
  • thescience.bystrickaya.ru/itogo-91-konkursnaya-dokumentaciya.html
  • laboratornaya.bystrickaya.ru/psihologicheskaya-sushnost-igri.html
  • turn.bystrickaya.ru/polozhenie-o-kontrolno-priemnom-apparate-po-realizacii-zakazovv-schet-hozyajstvennogo-soglasheniya-s-germaniej.html
  • occupation.bystrickaya.ru/muzikalnaya-estetika-srednevekovya-i-vozrozhdeniya.html
  • report.bystrickaya.ru/izveshenie-o-provedenii-zaprosa-kotirovok-74-postavka-knizhnoj-produkcii.html
  • credit.bystrickaya.ru/pisateli-dekabristi-tipovaya-uchebnaya-programma-dlya-visshih-uchebnih-zavedenij-po-specialnostyam-1-21-05-02-russkaya-filologiya.html
  • institute.bystrickaya.ru/faktori-deyatelnosti-vizivayushie-utomlenie-230102-avtomatizirovannie-sistemi-obrabotki-informacii-i-upravleniya.html
  • prepodavatel.bystrickaya.ru/tekst-iz-pyati-magnitofonnih-kasset-stranica-10.html
  • tests.bystrickaya.ru/metodicheskie-rekomendacii-yaroslavl-2010-bbk-74-202-4-c-19.html
  • studies.bystrickaya.ru/abramov-s-i-investirovanie.html
  • lecture.bystrickaya.ru/analiz-novelli-izmena-iz-proizvedeniya-babelya-konarmiya.html
  • credit.bystrickaya.ru/oficialnaya-informaciya-normativnie-dokumenti-ria-novosti-18.html
  • exchangerate.bystrickaya.ru/fenomen-nlo-chast-7.html
  • notebook.bystrickaya.ru/istoriya-antichnoj-filosofii-stranica-4.html
  • bukva.bystrickaya.ru/spisok-sokrashenij-svodnie-dannie-mezhdunarodnih-meropriyatij-v-oblasti-obrazovaniya-nauki-i-innovacij-na-200-9-g.html
  • education.bystrickaya.ru/252-stranovie-i-regionalnie-riski-660021-rossiya-krasnoyarskij-kraj-g-krasnoyarsk-bograda-144a-informaciya.html
  • paragraph.bystrickaya.ru/metodicheskie-rekomendacii-po-russkomu-yaziku-i-literature-dlya-postupayushih-v-mgsgi.html
  • credit.bystrickaya.ru/pase-gotovitsya-k-osennej-sessii-pervij-kanal-novosti-19-09-2008-sharafutdinov-maksim-06-00-07-00-08-00-6.html
  • upbringing.bystrickaya.ru/meropriyatiya-v-centralnom-federalnom-okruge-vserossijskie-meropriyatiya-2006-g-4-stranica-15.html
  • klass.bystrickaya.ru/astahovaev-mi-otkriti-ili-razmishleniya-o-neprerivnom-obrazovanii-ekaterina-astahova-sloboda-2005-8apr-28-s10.html
  • learn.bystrickaya.ru/glava-xxi-pravovie-sistemi-sovremennosti-reshenie-etoj-blagorodnoj-zadachi-bilo-bi-nevozmozhnim-bez-aktivnoj-pomoshi.html
  • uchenik.bystrickaya.ru/denezhnie-edinici-raznih-stran.html
  • reading.bystrickaya.ru/mehanizm-vzimaniya-naloga-na-dohodi-fizicheskih-lic.html
  • paragraph.bystrickaya.ru/kulturnaya-revolyuciya.html
  • uchitel.bystrickaya.ru/razrabotka-metodov-sovmestnogo-primeneniya-geneticheskogo-i-avtomatnogo-programmirovaniya.html
  • reading.bystrickaya.ru/metodi-issledovaniya-bessoznatelnogo-po-z-frejdu.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.