813

Особенности использование кодов

Практическая работа

Информатика, кибернетика и программирование

Создать алфавит А, используемый при форматировании Ф.И.О., которые будут являться исходным текстом. Построить прямые двоичные коды постоянной длины и закодировать ими исходный текст. Коды, учитывающие частоту символов. Коды Грея. Построение кода для обнаружения и исправления ошибок.

Русский

2013-01-06

170 KB

12 чел.

Задание 1.

Прямые коды.

Создать алфавит А, используемый при форматировании Ф.И.О., которые будут являться исходным текстом. Построить прямые двоичные коды постоянной длины и закодировать ими исходный текст.

 гущиналексейниколаевич     A = (гущиналексйовч)

                                         

таблица 1

                  

Символ

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

А

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

Щ

13

1101

                                        

    

I = [ ]

     N = 14

Для предметов каждого N символа ввиде 4-х разрядного кода. Рассмотрим возможные варианты из комбинации нуля и единицы.

1) все нули.

0000

2) одна единица и три нуля.

0001

0010

0100

1000

3) две единицы и два нуля.

0011

0110

1001

1010

0101

1100

4) три единицы и один ноль.

0111

1011

1101

       г              у            щ             и              н

Фамилия Гущин   0010 1011 1101 0100 1000

       а       л       е       к       с       е       й

Имя   Алексей  0000 0111 0011 0110 1010 0011 0101

                                                  н       и       к      о      л       а       е       в       и      ч       

Отчество Николаевич  1000 0100 0110 1001 0111 0000 0011 0001 0100 1100

Задание 2.

Коды, учитывающие частоту символов.

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

 таблица 2

Символ

Частота

Код

Е

3

0000

И

3

0001

А

2

0010

К

2

0011

Л

2

0100

Н

2

0101

В

1

0110

Г

1

0111

Й

1

1000

О

1

1001

С

1

1010

У

1

1011

Ч

1

1100

Щ

1

1101


Используя данный полученные в задание 1 кодируем каждую чистоту 4-х разрядным кодом. Назначим символами коды постоянной длины, число единиц , которых тем больше чем меньше чистота символа.

Гущин          0111 1011 1101 0001 0101

Алексей        0010 0100 0000 0011 1010 0000 1000

Николаевич  0101 0001 0011 1001 0100 0010 0000 0110 0001 1100

Задание 3.

Коды Грея.

 

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

являются кодами Грея.

 таблица 3

00

01

10

11

00

А

В

Г

Е

01

Л

К

Й

И

10

Н

О

С

У

11

Щ

Ч

         

Разместим в ячейках таблицы упорядоченные по алфавиту символы из множества А. Для формирования кода Грея каждому символу объединим номера строки и столбца ячейки, в которой находится символ.

таблица 4

Символ

Алфавита А

Код Грея

1

2

А

0000

В

0001

Г

0010

Е

0011

Л

0100

К

0101

Й

0110

И

0111

Н

1000

О

1001

С

1010

У

1011

Щ

1110

Ч

1111

Гущин   0010 1011 1110 0111 1000

Алексей   0000 0100 0011 0101 1010 0011 0110

Николаевич 1000 0111 0101 1001 0100 0000 0011 0001 0111 1111

Задание 4.

Метод простой подстановки.

Выполнить криптографическое кодирование исходного текста методом простой подстановки. Исходным алфавитом принять множество А (из задания 1).

Для построения кода составим таблицу соответствия между символами исходного алфавита А и произвольными 4-х разрядными кодами. Для упрощения процедуры используем произвольный номер символа алфавита А в пределах от 0 до 12.

таблица 5

Символы исходного

алфавита

Произвольный

номер символа

Коды

А

1

0001

В

5

0101

Г

3

0011

Е

2

0010

Л

4

0100

К

7

0111

И

10

1010

Й

8

1000

Н

14

1011

О

9

1001

С

6

0110

У

0

0000

Щ

11

1011

Ч

13

1101

Гущин   

Алексей    

Николаевич 

Задание 5.

Метод Вижинера

Выполнить криптографическое кодирование исходного текста методом Вижинера. Исходным алфавитом принять множество A (из задания 1). В качестве ключа кодирования использовать имя собственное. В качестве символов кодирования принять l-разрядные двоичные кодовые комбинации (величина l определена в задании 1), значение которых находится в пределах от 0 до двоичного эквивалента числа N-1 , где N – мощность алфавита A.

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

  1.  для построения кода пронумеруем символы исходного алфавита, начиная с 0, и каждому десятичному номеру сопоставим двоичный эквивалент размером l.

Получим таблицу соответствия (табл.9),

Таблица 9.

                                                                                                                                               

 

символы исходного алфавита

А

В

Г

Е

И

Й

К

Л

Н

О

С

У

десятичные номера символов

0

1

2

3

4

5

6

7

8

9

10

11

12

13

двоичные номера символов

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

  1.    для кодирования выполняем шаги:

- выписываем исходный текст (строка 1 табл. 10),

- формируем номера символов исходного текста из табл. 9 (строка 2 табл. 10),

- многократно записываем ключ под исходным текстом (строка 3 табл.10),

- заполняем номера символов ключа из табл. 9 (строка 4 табл.10),

- складываем по модулю 13 (это мощность множества A) номера символов (строка 5 табл. 10),

- заменяем полученные числа символами исходного алфавита из табл. 9 (строка 6 табл. 10). Таким образом, получаем строку, соответствующую исходному тексту:

ччлпвиввголдпгдлвпофгфлги.

                                                                                                     

                                                                                                      

                                                                                                       Таблица 10.

Номер строки

Результаты выполнения

1

Ф

И

Л

И

П

П

О

В

В

Л

А

Д

И

С

Л

А

В

О

Л

Е

Г

О

В

И

Ч

2

10

5

6

5

8

8

7

1

1

6

0

3

5

9

6

0

1

7

6

4

2

7

1

5

11

3

В

Л

А

Д

И

С

Л

А

В

В

Л

А

Д

И

С

Л

А

В

В

Л

А

Д

И

С

Л

4

1

6

0

3

5

9

6

0

1

1

6

0

3

5

9

6

0

1

1

6

0

3

5

9

6

5

11

11

6

8

1

5

1

1

2

7

6

3

8

2

3

6

1

8

7

10

2

10

6

2

5

6

Ч

Ч

Л

П

В

И

В

В

Г

О

Л

Д

П

Г

Д

Л

В

П

О

Ф

Г

Ф

Л

Г

И

- Заменяем символы строки (12) двоичными номерами из табл. 9. Получаем результат (отдельно закодирована фамилия, имя и отчество):

Филиппов – 1011, 1011, 0110, 1000, 0001, 0101, 0001, 0001.

Владислав – 0010, 0111, 0110, 0011, 1000, 0010, 0011, 0110, 0001.

Олегович – 1000, 0111, 1010, 0010, 1010, 0110, 0010, 0101.

                                      Задание 8.

          Построение кода для обнаружения ошибок.

 

      Построить помехозащитный код для обнаружения ошибок кратности 1 для символов алфавита А(из задания 1). Выполнить кодирование исходного текста и продемонстрировать помехозащитные свойства построенного кода.

  1.  Для кода указанной корректирующей способностью кодовое расстояние d должно удовлетворять соотношению: d≥2. Для построения кода используем схему построения кода  Грея и кода символов исходного алфавита из таблицы 7.

                                                                                    Таблица 15

Номера строк

    Номера столбцов

Полученные коды

0

1

0000

А

00000

0001

В

00011

0011

Г

00110

0010

Д

00101

0110

Е

01100

0111

И

01111

0101

Л

01010

0100

О

01001

1100

П

11000

1101

С

11011

1111

Ф

11110

1110

Ч

11101

Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода.

                                      Таблица 16

В

И

Л

О

А

В

|||||

2

2

2

2

И

|||||

2

2

4

Л

|||||

2

2

О

|||||

2

Филиппов-11110, 01111, 01010, 01111, 11000, 11000, 01001, 00011.

Владислав-00011, 01010, 00000, 00101, 01111, 11011, 01010, 00000, 00011.

Олегович-01001, 01010, 01100, 00110, 01001, 00011, 01111, 11101.

Для проверки корректирующей способности  кода предложим, что на передаваемую кодовую комбинацию 00101 (символ  Д) накладывается ошибка кратности 1 :

                                00101 – 00001= 00100

Полученный код не принадлежит кодовым комбинациям из таблицы 15.

Задание 9.

Построение кода для исправления ошибок.

Построить помехозащитный код для исправления ошибок кратности 1 для символов алфавита А ( из задания 1 ). Продемонстрировать помехозащитные свойства построенного кода.

  1.  для кода с указанной корректирующей способностью кодовое  расстояние d должно удовлетворять соотношению:  d ≥ 3. Для построения кода используем схему построения кода  Грея, коды символов исходного алфавита из таблицы 15 и саму схему решения задачи из задания 8.

                                                                                             Таблица  17

Номера    строк

Номера столбцов

Полученные    коды

0000

0001

0011

0010

0110

00000

В

000000000

00011

И

000110001

00110

Л

001100011

00101

О

001010010

01100

А

011000110

Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода.

                                       Таблица 18

В

И

Л

О

А

В

|||||

3

4

3

4

И

|||||

3

4

7

Л

|||||

3

4

О

|||||

3

Для проверки корректирующей способности  кода предложим, что на передаваемую кодовую комбинацию 001100011 (символ Л) накладывается ошибка кратности 1 :

                                001100011-000000001=001100010

  Поскольку полученный код не принадлежит кодовым комбинациям из таблицы 17, она определяется как искаженный.

Рассчитывается  расстояние  между  разрешенными кодовыми комбинациями и искаженным кодом.

                                                  Таблица 19   

Искаженный

код

В

И

Л

О

А

000110000

2

1

4

3

6

По таблице 19 определяется тот символ, для которого расстояние между соответствующими кодами равно 1,  поскольку именно такова кратность ошибки, которую данные кол должен исправить.

                                 000110000→001100011

Предположим, что на передаваемую кодовую комбинацию 001100011 (символ Л) накладывается ошибка кратности 2, искажающая два младших разряда:

                        ……………- 000000011=

Поскольку полученный код не принадлежит кодовым комбинациям из таблицы 17, он определяется как искаженный.


 

А также другие работы, которые могут Вас заинтересовать

23756. Наибольший общий делитель 69.5 KB
  Основная цель: тренировать способность к нахождению НОД на основе разложения чисел на простые множители способность к рефлексии собственной деятельности; повторить и закрепить решение уравнений решение задач методом уравнений графическое изображение множеств с помощью диаграммы Венна. Какой темой мы занимались на предыдущих уроках Нахождение НОД чисел методом разложения чисел на простые множители. Чему равен НОД взаимно простых чисел НОД взаимно простых чисел равен 1. Найдите: а НОД а b; б НОД b с; в НОД а с.
23757. Открытие нового знания 49.5 KB
  Можно ли утверждать что числа a b и c кратны числу 14 a = b = c = Числа a и b кратны числу 14 т. в разложении этих чисел есть множители числа 14 а число с нет т. в нём не содержится разложения числа 14. Найдите частное от деления числа a на число 14 числа b на число 14.
23758. Открытие нового знания 38 KB
  Здравствуйте ребята Какая основная задача стояла перед нами на прошлых уроках Мы вывели новый способ нахождения НОК используя разложение чисел на простые множители. Сегодня на уроке мы продолжим работать над нахождением НОК чисел и рассмотрим нахождение НОК разных чисел. Найдите НОК 15 24: а составляя множества К 15 и К 24; б перебирая кратные 24; в с помощью разложения чисел 15 и 24 на простые множители.
23759. Наименьшее общее кратное 73 KB
  Основная цель: тренировать способность к нахождению НОК на основе разложения чисел на простые множители способность к рефлексии собственной деятельности; повторить и закрепить распределительное свойство умножения правило деления произведения на число действия с многозначными числами формулы объема и площади поверхности куба. Чему мы научились на предыдущих уроках Мы учились находить НОД и НОК чисел разными способами. Сегодня вы будете проверять на сколько хорошо вы усвоили метод нахождения НОД и НОК используя разложения чисел на...
23760. Признак делимости на 3 и на 9 48 KB
  Основные цели: тренировать способность к доказательству общих утверждений на примере признаков делимости на 3 и на 9; повторить и закрепить изученные свойства и признаки делимости решение текстовых задач решение примеров на порядок действий построение формул зависимости между величинами. Какие признаки делимости мы изучили Признаки делимости на 2 на 5 на 10 на 4 на 8 на 25. А зачем нам нужны признаки делимости Что бы быстрее определять делится ли число на данное или нет.
23761. Признак делимости на 3 и на 9 57.5 KB
  А зачем нам нужны признаки делимости Что бы быстрее определять делится ли число на данное или нет. Затруднения могут быть при выполнении задания тех случаях где множитель не делится ни на 3 ни на 9 или делится только на 3. 54 делится на 3 и третье т. 15 делится на 3.
23762. Признак делимости на 9 43 KB
  А зачем нам нужны признаки делимости Что бы быстрее определять делится ли число на данное или нет. Будет ли число представленное выражением d 235 делиться на5 Всё зависит от того какое значение принимает d потому что если каждое слагаемое делится на 5 то и вся сумма разделится на 5 ели одно слагаемое делится на 5 а другое не делится на 5 то вся сумма не разделится на 5. 2 Будет ли число представленное выражением 271k делится на 2 Всё зависит какое значение принимает k т. по свойству делимости произведения...
23763. Признаки делимости на 10, на 2, на 5 87.5 KB
  1 Выберите из множества A = числа кратные: а 2 б 5 в 10 г и 2 и 5 и 10. Кратные 2: 110; 300; 404; 706 т. П1 Кратные 5: 110; 215; 300 т. На доске: П2 Кратные 10: 110; 300 т.
23764. Признаки делимости на 10, на 5, на 2 42 KB
  Выясните делится ли: 1 на 10; Делится на 10 т. 10 делится на 10 а произведение делится на число если один из множителей делится на число. 2 100a 10b на 5; Делится на 5 т. 100 делится на 5 а значит 100a делится на 5 10 делится на 5 а значит 10b делится на 5 следовательно вся сумма делится на 5 по свойству делимости суммы на число.