Для кодирования сообщения используется таблица: Как делать 5 задание егэ по информатике. Для кодирования сообщения, состоящего только из букв А, Б, В и Г

Содержание

Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода.

Автор материалов — Лада Борисовна Есакова.

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

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

Равномерное кодирование всегда однозначно декодируемо.

Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.

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

 

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

Пример 1.

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

1) 22162

2) 1020342

3) 2131453

4) 34017

Решение:

Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

О

В

Д

П

А

0

1

2

3

4

00

01

10

11

100

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.

Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Пример 2.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.

            1) D3A6

2) 62032206

3) 6A3D

4) CADBAADC

 

Решение:

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:

 

1101 0011 1010 01102 = D3A616

 

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Расшифровка сообщений

Пример 3.

Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

 

a

b

c

d

e

100

110

011

01

10

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:

1) cbade

2) acdeb

3) acbed

4) bacde

 

Решение

:

Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

Значит, будем перебирать варианты, пока не получим подходящее слово :

1) 100 011 01 10 110

Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.

Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.

Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.

 

Ответ: 2

Пример 4.

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась.

(Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

 

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

 

1) АххБ

2) АВхБ

3) хххх

4) АВББ

 

Решение:

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

Таким об­ра­зом, ответ: АВхБ.

Ответ: 2

Однозначное кодирование

Пример 5.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

1) 0001

2) 000

3) 11

4) 101

 

Решение:

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

 

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.

Ответ: 2

Пример 6.

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.

Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.

1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

2) ко­до­вое слово для буквы К можно со­кра­тить до 1

3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

4) это не­воз­мож­но

 

Решение:

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:


 

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ: 3

Ты нашел то, что искал? Поделись с друзьями!

Для кодирования сообщения, состоящего только из букв А, Б, В и Г – как решать

Формулировка задания: Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код. Если таким способом закодировать последовательность символов и записать результат в шестнадцатеричном коде, то получится…

Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код. Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:

  1. CDADBC
  2. A7C4
  3. 412710
  4. 4С7А

Решение:

Закодируем последовательность символов ВГАГБВ посимвольно с помощью таблицы:

В = 010

Г = 011

А = 00

Г = 011

Б = 11

В = 010

Значит последовательность равна:

Чтобы перевести последовательность в шестнадцатеричную систему, разобьем ее на группы по 4 символа:

И переведем каждую группу символов из двоичной в шестнадцатеричную:

01002 = 416

11002 = C16

01112 = 716

10102 = A16

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

Ответ: 4

Поделитесь статьей с одноклассниками «Для кодирования сообщения, состоящего только из букв А, Б, В и Г – как решать».

При копировании материалов с сайта ссылка на источник обязательна. Уважайте труд людей, которые вам помогают.
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.

A M N E O 000 11 01 001

a) Поименованная совокупность байтов на магнитом диске называется ФАЙЛОМ

b) Программа – это описание последовательности действий, который должен выполнить компьютер для решения поставленной задачи обработки данных.

c) Имя файла, как правило, состоит из двух частей, разделенных точкой: собственно имени файла и расширения.

d) Каталоги бывают вложенными в дург друга.

e) Программы для компьютера пишет программист.

Шестнадцатиричное число отображается в двоичную систему счисления путем представления каждой шестнадцатиричной цифры в виде тетрады — группы из четырех двоичных цифр. В самой левой тетраде незначащие двоичные нули отбрасываются.
Наименьшее четырехзначное шестнадцатиричное число — это 1000(16). Его двоичная запись 0001 0000 0000 0000(2) или 1 0000 0000 0000(2).
Но по условию нулей должно быть не 12, а семь, поэтому «лишние» пять нулей заменяем единицами. Поскольку число должно быть наименьшим, единицы ставим справа: 1 0000 0001 1111(2).
Осталось заменить каждую тетраду шестнадцатиричной цифрой: 101F(16)
Ответ: 101F

#include

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        if (n % i == 0)
        {
            cout << i << » «;
        }
    }
}

Здесь подходит ответ с)
(неX) ∧ (неY) ∧ (неZ)

1) 0 ∧ 0 ∧ 1 = 0       F=0   (первая строка таблицы истинности)
2) 0 ∧ 1 ∧ 0 = 0       F=0   (вторая строка)
3) 1 ∧ 0 ∧ 0 = 0       F=0   (третья)

Ответ:  с.     (неX) ∧ (неY) ∧ (неZ)

Прилагаю лист Excel (рабочий!!!)  и скриншот

Ответ:

пользователь

Объяснение:

ответ содержится в самом вопросе

Примеры кодирования | Практическая информатика

Среди всего разнообразия информации, обрабатываемой на компьютере, значительную часть составляют числовая, текстовая, графическая и аудиоинформация. Познакомимся с некоторыми способами кодирования этих типов информации в ЭВМ.

Кодирование чисел

Существуют два основных формата представления чисел в памяти компьютера. Один из них используется для кодирования целых чисел, второй (так называемое представление числа в формате с плавающей точкой) используется для задания некоторого подмножества действительных чисел.

Множество целых чисел, представимых в памяти ЭВМ, ограничено. Диапазон значений зависит от размера области памяти, используемой для размещения чисел. В k-разрядной ячейке может храниться 2k различных значений целых чисел.

Чтобы получить внутреннее представление целого положительного числа N, хранящегося в k-разрядном машинном слове, необходимо:

1)  перевести число N в двоичную систему счисления;
2)  полученный результат дополнить слева незначащими нулями до k разрядов.


Пример

Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке.

Переведем число в двоичную систему: 160710 = 110010001112. Внутреннее представление этого числа в ячейке будет следующим: 0000 0110 0100 0111.

Для записи внутреннего представления целого отрицательного числа (-N) необходимо:

1)  получить внутреннее представление положительного числа N;
2)  обратный код этого числа заменой 0 на 1 и 1 на 0;
3)  полученному числу прибавить 1.


Пример

Получим внутреннее представление целого отрицательного числа -1607. Воспользуемся результатом предыдущего примера и запишем внутреннее представление положительного числа 1607: 0000 0110 0100 0111. Инвертированием получим обратный код: 1111 1001 1011 1000. Добавим единицу: 1111 1001 1011 1001 — это и есть внутреннее двоичное представление числа -1607.

Формат с плавающей точкой использует представление вещественного числа R в виде произведения мантиссы m на основание системы счисления n в некоторой целой степени p, которую называют порядком: R = m * n p.

Представление числа в форме с плавающей точкой неоднозначно. Например, справедливы следующие равенства:

12.345 = 0.0012345 x 104 = 1234.5 x 10-2 = 0.12345 x 102

Чаще всего в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в таком представлении должна удовлетворять условию: 0. 1p <= m < 1p. Иначе говоря, мантисса меньше 1 и первая значащая цифра — не ноль (p — основание системы счисления).

В памяти компьютера мантисса представляется как целое число, содержащее только значащие цифры (0 целых и запятая не хранятся), так для числа 12.345 в ячейке памяти, отведенной для хранения мантиссы, будет сохранено число 12345. Для однозначного восстановления исходного числа остается сохранить только его порядок, в данном примере — это 2.

Кодирование текста

Множество символов, используемых при записи текста, называется алфавитом. Количество символов в алфавите называется его мощностью.

Для представления текстовой информации в компьютере чаще всего используется алфавит мощностью 256 символов. Один символ из такого алфавита несет 8 бит информации, т. к. 28 = 256. Но 8 бит составляют один байт, следовательно, двоичный код каждого символа занимает 1 байт памяти ЭВМ.

Все символы такого алфавита пронумерованы от 0 до 255, а каждому номеру соответствует 8-разрядный двоичный код от 00000000 до 11111111. Этот код является порядковым номером символа в двоичной системе счисления.

Для разных типов ЭВМ и операционных систем используются различные таблицы кодировки, отличающиеся порядком размещения символов алфавита в кодовой таблице. Международным стандартом на персональных компьютерах является уже упоминавшаяся таблица кодировки ASCII.

Принцип последовательного кодирования алфавита заключается в том, что в кодовой таблице ASCII латинские буквы (прописные и строчные) располагаются в алфавитном порядке. Расположение цифр также упорядочено по возрастанию значений.

Стандартными в этой таблице являются только первые 128 символов, т. е. символы с номерами от нуля (двоичный код 00000000) до 127 (01111111). Сюда входят буквы латинского алфавита, цифры, знаки препинания, скобки и некоторые другие символы. Остальные 128 кодов, начиная со 128 (двоичный код 10000000) и кончая 255 (11111111), используются для кодировки букв национальных алфавитов, символов псевдографики и научных символов. О кодировании символов русского алфавита рассказывается в главе «Обработка документов».

Кодирование графической информации

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

Растровые изображения представляют собой однослойную сетку точек, называемых пикселами (pixel, от англ. picture element). Код пиксела содержит информации о его цвете.

Для черно-белого изображения (без полутонов) пиксел может принимать только два значения: белый и черный (светится — не светится), а для его кодирования достаточно одного бита памяти: 1 — белый, 0 — черный.

Пиксел на цветном дисплее может иметь различную окраску, поэтому одного бита на пиксел недостаточно. Для кодирования 4-цветного изображения требуются два бита на пиксел, поскольку два бита могут принимать 4 различных состояния. Может использоваться, например, такой вариант кодировки цветов: 00 — черный, 10 — зеленый, 01 — красный, 11 — коричневый.

На RGB-мониторах все разнообразие цветов получается сочетанием базовых цветов — красного (Red), зеленого (Green), синего (Blue), из которых можно получить 8 основных комбинаций:

RGBцвет
0  0  0  черный
0  0  1  синий
0  1  0  зеленый
0  1  1  голубой
RGBцвет
1  0  0  красный
1  0  1  розовый
1  1  0  коричневый
1  1  1  белый

Разумеется, если иметь возможность управлять интенсивностью (яркостью) свечения базовых цветов, то количество различных вариантов их сочетаний, порождающих разнообразные оттенки, увеличивается. Количество различных цветов — К и количество битов для их кодировки — N связаны между собой простой формулой: 2N = К.

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

Объекты векторного изображения, в отличии от растровой графики, могут изменять свои размеры без потери качества (при увеличении растрового изображения увеличивается зернистость). Подробнее о графических форматах рассказывается в разделе «Графика на компьютере».

Кодирование звука

Из курса физики вам известно, что звук — это колебания воздуха. Если преобразовать звук в электрический сигнал (например, с помощью микрофона), мы увидим плавно изменяющееся с течением времени напряжение. Для компьютерной обработки такой — аналоговый — сигнал нужно каким-то образом преобразовать в последовательность двоичных чисел.

Поступим следующим образом. Будем измерять напряжение через равные промежутки времени и записывать полученные значения в память компьютера. Этот процесс называется дискретизацией (или оцифровкой), а устройство, выполняющее его — аналого-цифровым преобразователем (АЦП).

Для того чтобы воспроизвести закодированный таким образом звук, нужно выполнить обратное преобразование (для него служит цифро-аналоговый преобразователь — ЦАП), а затем сгладить получившийся ступенчатый сигнал.

Чем выше частота дискретизации (т. е. количество отсчетов за секунду) и чем больше разрядов отводится для каждого отсчета, тем точнее будет представлен звук. Но при этом увеличивается и размер звукового файла. Поэтому в зависимости от характера звука, требований, предъявляемых к его качеству и объему занимаемой памяти, выбирают некоторые компромиссные значения.

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

Человек издавна использует довольно компактный способ представления музыки — нотную запись. В ней специальными символами указывается, какой высоты звук, на каком инструменте и как сыграть. Фактически, ее можно считать алгоритмом для музыканта, записанным на особом формальном языке. В 1983 г. ведущие производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI.

Конечно, такая система кодирования позволяет записать далеко не всякий звук, она годится только для инструментальной музыки. Но есть у нее и неоспоримые преимущества: чрезвычайно компактная запись, естественность для музыканта (практически любой MIDI-редактор позволяет работать с музыкой в виде обычных нот), легкость замены инструментов, изменения темпа и тональности мелодии.

Заметим, что существуют и другие, чисто компьютерные, форматы записи музыки. Среди них следует отметить формат MP3, позволяющий с очень большим качеством и степенью сжатия кодировать музыку. При этом вместо 18—20 музыкальных композиций на стандартный компакт-диск (CDROM) помещается около 200. Одна песня занимает примерно 3,5 Mb, что позволяет пользователям сети Интернет легко обмениваться музыкальными композициями.

Задания для выполнения работы — Информатика, информационные технологии

ОБРАЗОВАТЕЛЬНАЯ АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОРГАНИЗАЦИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛЖСКИЙ УНИВЕРСИТЕТ ИМЕНИ В.Н. ТАТИЩЕВА»

(ИНСТИТУТ)

Кафедра «Информатика и системы управления»

«УТВЕРЖДАЮ»

Проректор по учебной работе

______________ А.Д. Немцев

_____________ 2012 г.

ИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ

Лабораторный практикум

Тольятти 2012

О.Ю. Федосеева. Лабораторный практикум по дисциплине «Информатика и информационные технологии в профессиональной деятельности» — Тольятти, Волжский университет имени Татищева, 2012г. — 134 с.

Лабораторный практикум разработан для студентов специальности 030901 «Правовое обеспечение национальной безопасности» с целью оказания методической помощи при выполнении лабораторных работ по дисциплине «Информатика и информационные технологии в профессиональной деятельности». Рассмотрены основные понятия и определения количества информации, кодирования информации, алгоритмизации, основные приемы программирования на языке Turbo Pascal, приемы работы в операционной системе Windows 7, правила перевода чисел из одной системы счисления в другую, арифметических операций над числами в различных системах счисления, основные приемы работы в программах MS Office 2007 (Word, Excel, Access, PowerPoint), Paint.

Рассмотрено и утверждено на заседании кафедры «Информатика и системы управления»

Протокол № ____ от «_____»_____________ 2012г.

Зав. кафедрой, д.т.н., профессор______________________С.В. Краснов

Одобрено Учебно-методическим советом факультета

Протокол № _____ от «____» _________ 2012г.

Председатель____________________________________О.Ю. Федосеева

Одобрено Учебно-методическим советом университета

Протокол № _____ от «____» _________ 2012г.

Председатель_____________________________________А.Д. Немцев

a Волжский университет имени В.Н. Татищева

Перечень разделов и тем по дисциплине

Лабораторная работа №1
Тема: КОЛИЧЕСТВО ИНФОРМАЦИИ. КОДИРОВАНИЕ ИНФОРМАЦИИ

Цель работы:Изучить основные понятия по теме: информация, количество информации, свойства информации, кодирование информации.

Задание:

1. Изучить основные единицы измерения количества информации.

2. Изучить основные способы кодирования информации.

Литература:[1]-стр. 5-15, [2]-стр. 19-27.

Задания для выполнения работы

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

2). Вычесть найденный номер из числа 34; 3). Полученное число будет порядковым номером буквы в алфавите в закодированном сообщении; 4) используя шаги 1–3, закодировать все буквы исходного сообщения. В результате кодирования по заданному алгоритму исходное сообщение «СЛОН» преобразуется в сообщение…

«НУРС»
«МУРС»
«МУРТ»
«НТУР»

Решение: Для определения номера буквы в алфавите воспользуемся таблицей

Буква «С», номер в алфавите 19, номер закодированной буквы . Закодированная буква – «Н». Буква «Л», номер в алфавите 13, номер закодированной буквы . Закодированная буква – «У». Буква «О», номер в алфавите 16, номер закодированной буквы . Закодированная буква – «Р». Буква «Н», номер в алфавите 15, номер закодированной буквы . Закодированная буква – «С». Таким образом, имеем закодированное сообщение «НУРС».

2. Для установления соответствия между символами (буквами, цифрами, знаками и т.д.) и двоичными кодами в компьютере используются …

кодовые таблицы
электронные словари
файлы с описанием начертания символов, находящиеся на жестком диске
растровые маски символов, находящиеся в ОЗУ компьютера

Решение: При хранении в компьютере любой текст, документ, статья, книга рассматривается как линейная последовательность символов. Каждому символу из этой последовательности ставится в соответствие конкретный двоичный код, состоящий из 8, 16 и более двоичных разрядов. Списки всех используемых для записи текстов символов и соответствующих им двоичных кодов (чисел) образуют кодовые таблицы.

3. Символы некоторого алфавита кодируются двух-, трех- и четырехзначными двоичными кодами. Тогда максимальное количество символов алфавита, которые можно закодировать данными комбинациями, составит …

Решение: Для решения задачи заметим, что количество двузначных двоичных кодов составит , трехзначных , четырехзначных . Таким образом, максимальное количество возможных комбинаций составит .

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

алфавитом
кодовой таблицей
символьной таблицей
синтаксисом

5. Некоторый алгоритм кодирования однозначно заменяет каждую букву русского алфавита в исходном сообщении на другую букву русского алфавита. Тогда сообщение «МАСЛО, ЛОШАДЬ» в закодированном виде будет иметь вид …

ХРЮНЯ, НЯФРИК
СЛОНЯ, МУМРИК
БРЫСЯ, ЯСКРЮН
НЯФКА, МУЛЯКА

Решение: Для выбора правильного варианта достаточно заметить, что в исходном сообщении две последние буквы первого слова совпадают с двумя первыми буквами второго слова. Также совпадают вторая буква в первом слове и четвертая буква во втором слове. В закодированном сообщении должны быть такие же совпадения. Под это описание подходит только закодированное сообщение «ХРЮНЯ, НЯФРИК».

6. Всего в таблице ASCII может содержаться 256 однобайтовых кодов символов. Первые 128 однобайтовых кодов определены для прописных и строчных латинских букв и специальных знаков. Вторые 128 кодов предназначаются …

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

Решение: Таблица ASCII состоит из двух частей. Всего в таблице ASCII содержится 256 однобайтовых кодов символов. Стандарт кодовой таблицы ASCII определяет первые 128 символов и соответствующих им кодов – базовую часть таблицы ASCII. Первые 128 однобайтовых кодов определены для прописных и строчных латинских букв и специальных знаков («пробел», «№» «#» «~» и других), скобок и знаков препинания, а также для специальных управляющих символов (табуляция, перевод строки, возврат каретки). Вторая часть таблицы из 128 кодов используется для определения дополнительных символов, в том числе и для символов национальных алфавитов.

7. Символы (буквы, цифры, знаки и т.д.) в компьютере кодируются установлением соответствия между символом и …

двоичным кодом (числом). Список всех соответствий содержится в кодовой таблице
некоторым словом (А – аз, Б – буки и т.д.). Список всех соответствий держится в тезаурусе
файлом с описанием начертания символа. Все файлы находятся на жестком диске
растровой маской. Все соответствия находятся в ОЗУ компьютера

8. Для кодирования слова КОМПЬЮТЕР с помощью таблицы UNICODE понадобится …

18 байт
18 бит
9 байт
145 бит

Решение: В кодовой таблице UNICODE каждому символу ставится в соответствие шестнадцатиразрядное двоичное (двухбайтовое) число. Таким образом, для кодирования слова КОМПЬЮТЕР с помощью таблицы UNICODE понадобится байт.

9. Объем памяти для хранения слова ПРОТОКОЛ, закодированного с помощью кодовой таблицы UNICODE, при перекодировании его с помощью кодовой таблицы Windows-1251 …

уменьшится в 2 раза
увеличится в 2 раза
не изменится
уменьшится на 2 байта

Решение: В кодовой таблице UNICODE каждому символу ставится в соответствие шестнадцатиразрядное (двухбайтовое) двоичное число. Таким образом, для кодирования слова ПРОТОКОЛ с помощью таблицы UNICODE понадобится байт. Кодовая таблица Windows-1251 является вариантом таблицы ASCII, и в ней каждому символу ставится в соответствие восьмиразрядное (однобайтовое) двоичное число. Для кодирования слова КОМПЬЮТЕР с помощью таблицы Windows-1251 понадобится байт. Следовательно, объем необходимой памяти уменьшится в 2 раза.

10. Для кодирования всех возможных символов различных национальных алфавитов, а также символов, используемых в математических, физических и других специальных текстах, используется кодовая таблица …

UNICODE
Windows-1251
DOS
KOI-8

11. Для кодирования символов национальных алфавитов используется …

вторая часть кодовой таблицы ASCII
дополнительная кодовая таблица
первая часть кодовой таблицы ASCII
кодовая таблица ANSI

12. Всего в таблице ASCII может содержаться 256 однобайтовых кодов символов. Первые 128 однобайтовых кодов определены для прописных и строчных латинских букв и специальных знаков. Вторые 128 кодов предназначаются …

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

Задания для выполнения:

Задание 1. Считая, что каждый символ кодируется 16-ю битами, оцените информационный объем следующей пушкинской фразы в кодировке Unicode:

Привычка свыше нам дана: Замена счастию она.

44 бита 704 бита 44 байта 704 байта

Задание 2. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 50 различных сигналов?

Задание 3. Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

80 бит 70 байт 80 байт 560 байт

Задание 4. В кодировке Unicode на каждый символ отводится два байта. Определите информационный объем слова из двадцати четырех символов в этой кодировке.

384 бита 192 бита 256 бит 48 бит

Задание 5. В кодировке Unicode на каждый символ отводится два байта. Определите информационный объем слова из 32 символов в этой кодировке.

32 бит 64 бит 512 байт 512 бит

Задание 6. В кодировке Unicode на каждый символ отводится два байта. Определите информационный объем слова из 15 символов в этой кодировке.

15 байт 480 бит 240 бит 30 бит

Задание 7.Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

Задание 8. В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?

1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт

Задание 9. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?

Задание 10.Каждый символ в Unicode закодирован двухбайтным словом. Определите информационный объем следующего предложения в этой кодировке: Без охоты не споро у работы.

1) 28 байт 2) 28 бит 3) 448 байт 4) 448 бит

Задание 11.Для передачи секретного сообщения используется код, состоящий из строчных букв латинского алфавита. При этом все буквы кодируются одним и тем же (минимально возможным) количеством бит. Определите информационный объем сообщения длиной в 150 символов.

1) 208 бит 2) 750 бит 3) 8 бит 4) 150 байт

Задание 12. В кодировке ASCII на каждый символ отводится один байт. Определите информационный объем следующего высказывания Рене Декарта:Я мыслю, следовательно, существую.

1) 34 бита 2) 34 байта 3) 68 бит 4) 68 байт

Задание 13.Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено» «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 30 различных сигналов?

Задание 14.Для передачи секретного сообщения используется код, состоящий из строчных и прописных букв латинского алфавита. При этом все цифры кодируются одним и тем же (минимально возможным) количеством бит.

Определите информационный объем сообщения длиной в 100 символов.

1) 600 бит 2) 500 бит 3) 182 бита 4) 100 байт

Задание 15.

Задание 16.

Задание 17.

Задание 18.

Задание 19. Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

Задание 20. Алгоритм кодирования сообщения на английском языке имеет вид: 1) Используя таблицу , находим порядковый номер в латинском алфавите для буквы исходного сообщения; 2) номер латинской буквы вычитается из 31; 3) полученное число будет порядковым номером в русском алфавите буквы в закодированном сообщении согласно таблице .

Закодированному по данному алгоритму сообщению «ЮЕЛЬ» соответствует исходное сообщение …

«BYTE»
«BYIT»
«BAIT»
«BAYT»

Задание 21. Алгоритм кодирования сообщения имеет вид: 1) Используя таблицу, находят порядковые номера в русском алфавите всех букв исходного сообщения.

2) Из номеров букв, стоящих в сообщении на нечетных местах, вычитается число 2, к номерам букв, стоящих в сообщении на четных местах, добавляется число 2. Если полученный номер больше 33, то из него вычитаем 33, если полученный номер меньше 1, то прибавляем его к 33. 3) Полученные числа будут порядковыми номерами в русском алфавите букв в закодированном сообщении. Закодированному по данному алгоритму сообщению «БМН» соответствует исходное сообщение …

«ГОЛ»
«ДОМ»
«ДНО»
«ДОЛ»

Задание 22. Алгоритм кодирования сообщения имеет вид: Каждая буква исходного сообщения заменяется двузначным числом, первая цифра – номер строки таблицы, в которой находится буква, вторая цифра – номер столбца таблицы, в котором находится буква. Представлена следующая таблица: .

В закодированном сообщении полученные коды букв записываются подряд. Например, для буквы «У» номер строки – 4, номер столбца – 2. Код, соответствующий букве «У», – 42. В результате кодирования по заданному алгоритму исходное сообщение «СОВА» преобразуется в сообщение …

«40 33 11 10»
«40 10 12 10»
«40 33 12 10»
«40 33 12 11»

Задание 23. Сообщение закодировано согласно следующему алгоритму: каждая буква исходного сообщения заменяется двузначным числом, первая цифра – номер строки таблицы, в которой находится буква, вторая цифра – номер столбца таблицы, в котором находится буква. Таблица представлена на рисунке .

В закодированном сообщении полученные коды букв записываются подряд. Например, для буквы «У» номер строки – 4, номер столбца – 5. Код, соответствующий букве «У», – 45. Принято закодированное по данному алгоритму сообщение «43 45 24 11». Тогда исходное сообщение имеет вид …

«ЛУНА»
«ПУНА»
«ЛУМА»
«ЛУЗА»

Лабораторная работа №2

Тема: СТАНДАРТНЫЕ ПРИЛОЖЕНИЯ WINDOWS XP

Цель работы:

Ознакомиться со стандартными приложениями Windows XP: текстовым редактором Блокнот, графическим редактором Paint, текстовым процессором Word Pad.

Задание:Приобрести навыки работысо стандартными приложениями Windows XP: текстовым редактором Блокнот, графическим редактором Paint, текстовым процессором Word Pad, сопоставления приемов внедрения и связывания объектов, контроля загруженности процессора.

Литература:[1]-стр. 105-115, [2]-стр. 190-227.

Статьи к прочтению:

WORK-ZILLA.COM / Выполнение заданий на сайте воркзилла


Похожие статьи:

Двоичное кодирование информации

Двоичное кодирование информации

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

Теория кодирования близка к древнейшему искусству тайнописи – криптографии. Над разработкой различных шифров трудились многие известные ученые: философ Ф. Бэкон, математики Д.Кардано, Д. Валлис. Одновременно с развитием методов шифровки развивались приемы расшифровки, или криптоанализа.

В середине ХIХ в. ситуация изменилась. Изобретение телефона и искрового телеграфа поставило перед учеными и инженерами проблему создания новой теории кодирования. Первой ориентированной на технику системой кодирования оказалась азбука Морзе, в которой принято троичное кодирование (точка, тире, пауза).

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

Двоичный алфавит состоит из двух цифр 0 и 1.

Цифровые ЭВМ (персональные компьютеры относятся к классу цифровых) используют двоичное кодирование любой информации. В основном это объясняется тем, что построить техническое устройство, безошибочно различающее 2 разных состояния сигнала, технически оказалось проще, чем то, которое бы безошибочно различало 5 или 10 различных состояний.

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

 ДВОИЧНОЕ КОДИРОВАНИЕ СИМВОЛЬНОЙ (ТЕКСТОВОЙ) ИНФОРМАЦИИ

             Основная операция, производимая над отдельными символами текста — сравнение символов.

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

             Для кодирования текстов используются различные таблицы перекодировки. Важно, чтобы при кодировании и декодировании одного и того же текста использовалась одна и та же таблица.

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

Наиболее популярные таблицы перекодировки: ДКОИ-8, ASCII, CP1251, Unicode.

             Исторически сложилось, что в качестве длины кода для кодирования символов было выбрано 8 бит или 1 байт. Поэтому чаще всего одному  символу текста, хранимому в компьютере, соответствует один байт памяти.

Различных комбинаций из 0 и 1 при длине кода 8 бит может быть 28 = 256, поэтому с помощью одной таблицы перекодировки можно закодировать не более 256 символов. При длине кода в 2 байта (16 бит) можно закодировать 65536 символов.

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

   Традиционно для того чтобы закодировать один символ используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. При помощи формулы, которая связывает между собой количество возможных событий К и количество информации I, можно вычислить сколько различных символов можно закодировать (считая, что символы — это возможные события):

   К = 2I = 28 = 256,

   т. е. для представления текстовой информации можно использовать алфавит мощностью 256 символов.

   Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255.

   Необходимо помнить, что в настоящее время для кодировки русских букв используют пять различных кодовых таблиц (КОИ — 8, СР1251, СР866, Мас, ISO), причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой кодировке. Наглядно это можно представить в виде фрагмента объединенной таблицы кодировки символов.

   Одному и тому же двоичному коду ставится в соответствие различные символы.
Двоичный код Десятичный код КОИ8 СР1251 СР866 Мас ISO
11000010 194 б В — — Т

   Впрочем, в большинстве случаев о перекодировке текстовых документов заботится на пользователь, а специальные программы — конверторы, которые встроены в приложения.

   Начиная с 1997 г. последние версии Microsoft Windows&Office поддерживают новую кодировку Unicode, которая на каждый символ отводит по 2 байта, а, поэтому, можно закодировать не 256 символов, а 65536 различных символов.

   Чтобы определить числовой код символа можно или воспользоваться кодовой таблицей, или, работая в текстовом редакторе Word 6.0 / 95. Для этого в меню нужно выбрать пункт «Вставка» — «Символ», после чего на экране появляется диалоговая панель Символ. В диалоговом окне появляется таблица символов для выбранного шрифта. Символы в этой таблице располагаются построчно, последовательно слева направо, начиная с символа Пробел (левый верхний угол) и, кончая, буквой «я» (правый нижний угол).

   Для определения числового кода символа в кодировке Windows (СР1251) нужно при помощи мыши или клавиш управления курсором выбрать нужный символ, затем щелкнуть по кнопке Клавиша. После этого на экране появляется диалоговая панель Настройка, в которой в нижнем левом углу содержится десятичный числовой код выбранного символа.

1, 2, 3, код! — Задания цикла 3 — Урок 1.2. Как закодировать сообщение с номерами

Сводка

Студенты должны кодировать текстовое сообщение, используя только числа. Для этого они вносят предложения, а затем создают таблицу соответствия букв и цифр для использования всем классом. Они используют эту таблицу для кодирования сообщения, которое они отправляют, а также для декодирования сообщения, которое они получают.

Ключевые идеи
(см. Концептуальный сценарий )

«Информация»

  • Буква может быть представлена ​​числом.
  • Текст, состоящий из серии букв, может быть представлен серией цифр.
  • Кодирование текста означает замену букв соответствующими числами. Декодирование происходит наоборот.

Методы запросов

Эксперименты

Оборудование

Для учебной аудитории

Глоссарий

Таблица соответствия, кодирование, декодирование

Продолжительность

1 час 15 минут

Научные заметки о лексике до начала работы

  • В общем языке термины «кодирование», «кодирование» и «шифрование» часто используются неправильно или взаимозаменяемы.Термин «кодирование», например, иногда используется для обозначения «программирования» (или «написания кода»), «представления данных» (например, двоичного кодирования) или «изменения сообщения, чтобы сделать его непонятным» (как в секретный «код»).
  • Здесь мы будем использовать эти слова в соответствии с их научными определениями:
    • Кодирование означает представление данных. Во время этого урока студенты будут представлять сформулированное сообщение, используя числа. Когда они преобразуют буквы в числа, мы будем говорить о кодировке , а когда они сделают операцию в обратном порядке, мы будем говорить о кодировке .Это цель этого урока, а также следующих двух уроков по двоичному коду.
    • Шифрование сообщения заключается в его изменении, чтобы сделать его непонятным для непредусмотренных получателей (у которых нет ключа для его расшифровки). Это цель последовательности 3.4.
    • Термины шифрование / дешифрование (которых мы здесь будем избегать) обычно используются как синонимы для шифрования / дешифрования, тем более в повседневном языке, но есть нюанс. Криптоанализ, или расшифровка, заключается в том, что взламывает шифр зашифрованного сообщения (ключ угадывается кем-то, не предназначенным для доступа к нему).

Вводный вопрос

Учитель объясняет классу, что команда управления полетом общается с марсоходом и астронавтами с помощью электронных приборов. Эти инструменты могут отправлять и получать сообщения только цифрами, а не буквами. Соответственно, все сформулированное сообщение, которое должно быть отправлено, должно быть преобразовано в серию чисел перед отправкой (это операция кодирования), а затем преобразовано обратно в серию букв при получении (это операция декодирования).Между числами не должно быть пробелов или запятых: все числа «прилипли» друг к другу.

Возникает вопрос: как можно закодировать сформулированные сообщения как числа, а затем декодировать их?

Упражнение: Стратегия кодирования и декодирования (попарно)

Учитель говорит ученикам, что космонавты хотят продлить свое времяпровождение за пределы первоначально заявленного времени. Однако ветер усилился. Им нужно отправить сообщение в центр управления полетом с сообщением, которое начинается с:

ОТПРАВИТЬ ПОГОДНЫЙ СООБЩЕНИЕ.

Когда пара говорит, что они придумали стратегию кодирования, учитель тайно дает каждому ученику листок с коротким сообщением, содержащим хотя бы один пробел или точку, например «ИДТИ БЫСТРЕЕ», «ОЧЕНЬ ХОРОШО». или «ВСЕ В ХОРОШЕМ.». Они просят учеников закодировать сообщение для своего партнера, который затем должен его расшифровать. Учитель напоминает ученикам, что цифры в закодированном сообщении должны быть склеены вместе, без пробелов и знаков препинания.Два студента проверяют, правильно ли была передана информация. Если нет, пара работает над выявлением проблемы и изменением или улучшением своей стратегии.
Пятый класс, Кристель Крусберг, Шампиньи-сюр-Марн

Учебные заметки:

  • Кодируемый текст должен состоять только из букв, ЗАГЛАВНЫХ ЗАГЛАВНЫМИ буквами (без диакритических знаков), точек и пробелов. Соответственно, вполне вероятно, что большинство решений студентов будут включать привязку каждой буквы к числу в алфавитном порядке (1 = A, 2 = B и т. Д.)до 26 для Z) с дополнительными числами, соответствующими точкам и пробелам (например, 27 и 28 или 27 и 0).
  • Однако некоторые группы могут решить кодировать, используя разные числа для прописных букв (например, от 1 до 26) и строчных букв (например, от 27 до 52). Также может возникнуть проблема с акцентированными буквами и пунктуацией, отличными от точки. Хотя сообщение для кодирования не содержит цифр, некоторые группы могут попытаться учесть эту возможность. Они могут решить связать кодовые номера от 0 до 9 с номерами сообщений от 0 до 9 с кодировкой букв, начинающейся с 10.
  • Следует принять все эти возможности, даже если для простоты сообщение, данное учащимся, будет содержать только буквы, а кодировка будет одинаковой для всех вариантов буквы (например, A, и a оба закодированы с использованием 01) .
  • Некоторые студенты могут попытаться закодировать сообщение, используя менее интуитивное соответствие между текстом и числами, или даже создать систему, которая регулярно изменяется (например, система, которая меняется каждые 10 букв). Попросите этих студентов записать свои идеи для следующего урока (Последовательность 3.4).

Групповое обсуждение

Во время группового обсуждения учитель просит первую пару учеников рассказать классу о своем решении. Решения других групп сравниваются (см. «Примечания к обучению» выше), взвешивая «за» и «против» каждого из них. Затем класс приходит к консенсусу: таблица соответствия один-к-одному (без какой-либо двусмысленности во время кодирования или декодирования) между буквами, используемыми в сообщениях, и числами.

Таблица соответствия, выбранная для следующей части урока, следующая (обратите внимание, что фактически используемая таблица может варьироваться от одного класса к другому, особенно в отношении пробелов и точек):

Письмо A B С D E F G H
Номер 01 02 03 04 05 06 07 08
Письмо I Дж К L M N O-П
Номер 09 10 11 12 13 14 15 16
Письмо Q R S Т U В Вт Х
Номер 17 18 19 20 21 22 23 24
Письмо Y Z точка Космос
Номер 25 26 27 28

Обратите внимание, что числа от 1 до 9 (соответствующие буквам от A до I) были записаны от 01 до 09, так что все числа, используемые для кодирования букв, записываются с использованием одинакового количества цифр (т. е., два). Это означает, что 0221 следует читать как 02 21 и декодировать как BU; 2201 следует читать как 22 01 и декодировать как VA. Если буквы от A до I были написаны с использованием отдельных чисел от 1 до 9, текст, закодированный как 221, можно было бы прочитать как 2 21 или 22 1, которые затем можно было бы декодировать как BU или VA.

Упражнение — Кодирование сообщения (в группах)

Учитель раздает верхнюю часть Раздаточного материала 29 (таблица соответствия и Инструкция 1) и просит студентов закодировать сообщение для управления миссией (Инструкция 1), используя таблицу соответствия, выбранную классом.

После того, как сообщение закодировано, учитель публикует результаты и объявляет, что сообщение было отправлено в центр управления полетами. Они подчеркивают, что исходное сообщение и закодированное сообщение содержат одну и ту же информацию в двух разных формах.
Обсуждение со студентами, почему важно кодировать сообщения, используя два числа для каждой буквы.
Четвертый класс, Кэрол Винель, Париж

Задача — Расшифровка сообщения (по группам)

Учитель сообщает классу, что они только что получили ответ от центра управления полетом в закодированном сообщении.Теперь им нужно расшифровать ответ.

Учитель раздает нижнюю часть Раздаточного материала 29 (Инструкция 2) и дает ученикам время расшифровать сообщение.

Класс разделяет декодированное сообщение:

ПРЕДУПРЕЖДЕНИЕ ОБ ОСНОВНОМ ЦИКЛОНЕ. ВОЗВРАЩЕНИЕ НА БАЗУ. СКАЗАТЬ ОЖИДАЕМУЮ ЗАДЕРЖКУ.

Миссия не может быть продлена, и марсоход должен немедленно вернуться на базу.


Две стратегии декодирования: каждая буква по одной (слева) или каждое вхождение буквы в тексте (справа).
Пятый класс, Анн-Мари Лебрен, Бур-ла-Рейн

Преподавание:

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

Заключение и подведение итогов урока

Класс обобщает то, что они узнали на этом уроке:

  • Буква может быть представлена ​​числом.
  • Текст, который представляет собой последовательность букв, может быть представлен серией цифр.
  • Кодирование текста означает замену букв соответствующими числами. Декодирование происходит наоборот.

Студенты записывают эти выводы в свои научные тетради.Учитель добавляет то, что класс узнал о данных и алгоритмах, в «Определение информатики?» плакат.

Дальнейшее изучение

У старших школьников сообщение для декодирования может быть немного длиннее. Например, сообщение ниже представляет собой панграмму (все буквы алфавита включаются хотя бы один раз):

ВНИМАНИЕ. ГЛАВНЫЙ ЦИКЛОН ПРИБЛИЖАЕТСЯ БЫСТРО. ОЖИДАЕТСЯ БЕЗУМНЫЙ СИЛЬНЫЙ ВЕТЕР. ДОЛЖЕН БЫСТРО ВЕРНУТЬСЯ НА БАЗУ. СОВЕТУЙТЕ ETA.


Решено: Часть 1 — Матрицы криптографии могут быть использованы для кодирования…

Часть 1 — Криптография

Матрицы

могут использоваться для кодирования и декодирования сообщений. Начать с, мы могли бы присвоить цифры 1-26 буквам алфавит и присвойте цифру 0 пробелу между словами. Тогда мы может переводить любое словесное сообщение в строку чисел от 0 по 26. Ниже приводится таблица каждой буквы и соответствующей ей номер.

Пустой

А

Б

С

D

E

Ф

G

H

я

Дж

К

л

м

0

1

2

3

4

5

6

7

8

9

10

11

12

13

N

O

-П

квартал

R

S

т

U

В

Вт

Х

Я

Z

14

15

16

17

18

19

20

21

22

23

24

25

26

Мы будем использовать матрицу A ниже в качестве матрицы кодирования для нашего сообщения.

A = [1 1 1]
[2 1 2]
[3 3 1]

Введите матрицу кодирования A в свою электронную таблицу и обозначьте это.

Предположим, мы хотим закодировать сообщение «СЕКРЕТНЫЙ КОД». Начать с перевод сообщения в числа с помощью переписки выше.

Теперь поместите эти числа в матрицу B , которая будет иметь 3 ряды. Начните с первого числа в верхнем левом углу и двигайтесь вниз первый столбец, пока у вас не будет 3 строки. Когда вы заполняете столбец, начать сначала во втором столбце.Заполните матрицу B с помощью номера, соответствующие сообщению. Если нужно, добавьте лишние пробелы в конце сообщения для заполнения матрицы.

Создайте матрицу B в своей электронной таблице и убедитесь, что обозначьте это.

Чтобы закодировать сообщение, просто возьмите матрицу, содержащую наши сообщение, матрица B , и умножьте слева на матрица кодирования A . С помощью Excel найдите матрицу AB и подпишите Это.

Теперь наше сообщение «СЕКРЕТНЫЙ КОД» закодировано и представлены числами в матрице AB .-1 x (AB), чтобы увидеть, что ты получаешь.

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

52

28

28

25

27

35

22

89

47

36

50

41

50

37

110

46

68

35

71

75

36

Введите эту матрицу в Excel и обозначьте ее C .

Мы хотим узнать исходное сообщение, которое было закодировано в как выглядит матрица C выше.

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

Используйте таблицу вверху, чтобы расшифровать сообщение и написать сообщение в электронной таблице Excel.

Теория информации | математика | Британника

Историческая справка

Интерес к концепции информации вырос непосредственно с появлением телеграфа и телефона.В 1844 году американский изобретатель Сэмюэл Ф. Морс построил телеграфную линию между Вашингтоном, округ Колумбия, и Балтимором, штат Мэриленд. Морс столкнулся со многими электрическими проблемами, когда отправлял сигналы через подземные линии передачи, но по необъяснимым причинам он столкнулся с меньшим количеством проблем, когда линии были подвешены на опорах. Это привлекло внимание многих выдающихся физиков, в первую очередь шотландца Уильяма Томсона (барон Кельвин). Точно так же изобретение телефона в 1875 году Александром Грэмом Беллом и его последующее распространение привлекло новых научных нотариусов, таких как Анри Пуанкаре, Оливер Хевисайд и Майкл Пупен, к проблемам, связанным с передачей сигналов по проводам. Большая часть их работы была выполнена с использованием анализа Фурье, метода, описанного далее в этой статье, но во всех этих случаях анализ был посвящен решению практических инженерных проблем систем связи.

Формальное изучение теории информации началось только в 1924 году, когда Гарри Найквист, исследователь из Bell Laboratories, опубликовал статью под названием «Некоторые факторы, влияющие на скорость телеграфа». Найквист понял, что каналы связи имеют максимальную скорость передачи данных, и вывел формулу для расчета этих скоростей в бесшумных каналах с конечной полосой пропускания.Еще одним пионером был коллега Найквиста Р.В.Л. Хартли, чья статья «Передача информации» (1928) заложила первые математические основы теории информации.

Настоящее рождение современной теории информации можно проследить до публикации в 1948 году книги Клода Шеннона «Математическая теория коммуникации» в журнале Bell System Technical Journal . Ключевым шагом в работе Шеннона было его осознание того, что для создания теории коммуникационные сигналы должны рассматриваться изолированно от смысла сообщений, которые они передают. Этот взгляд резко контрастирует с общепринятым представлением об информации, в котором значение играет важную роль. Шеннон также понял, что объем знаний, передаваемых сигналом, не связан напрямую с размером сообщения. Известной иллюстрацией этого различия является переписка между французским писателем Виктором Гюго и его издателем после публикации Les Misérables в 1862 году. Гюго отправил своему издателю открытку с единственным символом «?». Взамен он получил карточку с символом «!».В контексте отношений Хьюго со своим издателем и публикой эти короткие сообщения были наполнены смыслом; без такого контекста эти сообщения бессмысленны. Точно так же длинное законченное сообщение на идеальном французском языке передаст мало полезных знаний тому, кто понимает только английский.

Получите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подпишитесь сейчас

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

Не случайно Шеннон работал в Bell Laboratories. Практическим стимулом для его работы были проблемы, с которыми он столкнулся при создании надежной телефонной системы. Ключевой вопрос, на который нужно было ответить на заре развития телекоммуникаций, заключался в том, как лучше всего оптимизировать физическое оборудование, в частности, как передавать максимальное количество телефонных разговоров по существующим кабелям.До работы Шеннона факторы достижения максимального использования не были четко поняты. Работа Шеннона определила каналы связи и показала, как назначить им пропускную способность, не только в теоретическом смысле, когда отсутствуют помехи или шум, но также и в практических случаях, когда реальные каналы подвергаются действительному шуму. Шеннон вывел формулу, которая показывала, как ширина полосы канала (то есть его теоретическая пропускная способность) и его отношение сигнал / шум (мера помех) влияют на его способность передавать сигналы.При этом он смог предложить стратегии для максимального увеличения пропускной способности данного канала и показал пределы возможностей данной технологии. Это было очень полезно для инженеров, которые после этого могли сосредоточиться на отдельных случаях и понять конкретные возможные компромиссы.

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

Новаторская работа Шеннона, таким образом, представила множество ключевых идей, которыми с тех пор руководствовались инженеры и ученые. Хотя теория информации не всегда дает понять, как именно достичь конкретных результатов, теперь люди знают, какие вопросы стоит задавать, и могут сосредоточиться на областях, которые принесут наибольшую отдачу.Они также знают, на какие вопросы сложно ответить и в каких областях вряд ли можно получить большую отдачу от затраченных усилий.

С 1940-х и 1950-х годов принципы классической теории информации применялись во многих областях. В разделе «Приложения теории информации» рассматриваются достижения не только в таких областях телекоммуникаций, как сжатие данных и исправление ошибок, но и в отдельных дисциплинах физиологии, лингвистики и физики.Действительно, даже во времена Шеннона появилось много книг и статей, в которых обсуждалась взаимосвязь между теорией информации и такими областями, как искусство и бизнес. К сожалению, многие из этих предполагаемых отношений имели сомнительную ценность. Попытки связать теорию информации с каждой проблемой и каждой областью настолько обеспокоили самого Шеннона, что в редакционной статье 1956 года под названием «The Bandwagon» он выпустил следующее предупреждение:

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

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

2.5: Применение матриц в криптографии

Цели обучения

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

  1. кодирует сообщение, используя матричное умножение.
  2. декодирует закодированное сообщение, используя обратную матрицу и матричное умножение

Шифрование насчитывает около 4000 лет.Исторические свидетельства указывают на то, что китайцы, египтяне, индийцы и греки шифровали сообщения тем или иным образом для различных целей. Одна известная схема шифрования называется шифром Цезаря, также называемым шифром подстановки, который использовал Юлий Цезарь, включал сдвиг букв в алфавите, например замену A на C, B на D, C на E и т. Д. Для кодирования сообщения. Шифры подстановки слишком просты по конструкции, чтобы сегодня считаться безопасными.

В средние века европейские народы начали использовать шифрование.Различные методы шифрования использовались в США от Войны за независимость до Гражданской войны и до наших дней.

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

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

В наши дни алгоритм Хилла не считается безопасным методом шифрования; с современными технологиями сравнительно легко отказаться. Однако в 1929 году, когда она была разработана, современной вычислительной техники не существовало. Этот метод, с которым мы легко справляемся с помощью современных технологий, был слишком громоздким для ручных вычислений. Хилл изобрел механическую шифровальную машину, чтобы помочь с математикой; его машина опиралась на шестерни и рычаги, но так и не получила широкого распространения.В свое время метод Хилла считался сложным и мощным и является одним из многих методов, влияющих на методы, используемые сегодня. Другие методы шифрования в то время также использовали специальные кодирующие машины. Алан Тьюринг, пионер в области информатики в области искусственного интеллекта, изобрел машину, которая могла расшифровывать сообщения, зашифрованные немецкой машиной Enigma, помогая переломить ход Второй мировой войны.

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

Чтобы использовать матрицы при кодировании и декодировании секретных сообщений, наша процедура выглядит следующим образом.

Сначала мы преобразуем секретное сообщение в строку чисел, произвольно присвоив номер каждой букве сообщения.Затем мы преобразуем эту строку чисел в новый набор чисел, умножая строку на квадратную матрицу по нашему выбору, которая имеет инверсию. Этот новый набор чисел представляет закодированное сообщение.

Чтобы декодировать сообщение, мы берем строку закодированных чисел и умножаем ее на обратную матрицу, чтобы получить исходную строку чисел. Наконец, сопоставив числа с соответствующими буквами, мы получаем исходное сообщение.

В этом разделе мы будем использовать соответствие, показанное ниже, где буквы от A до Z соответствуют числам от 1 до 26, пробел представлен числом 27, а знаки препинания игнорируются.

\ [\ begin {array} {ccccccccccccc}
\ mathrm {A} & \ mathrm {B} & \ mathrm {C} & \ mathrm {D} & \ mathrm {E} & \ mathrm {F} & \ mathrm {G} & \ mathrm {H} & \ mathrm {I} & \ mathrm {J} & \ mathrm {K} & \ mathrm {L} & \ mathrm {M} \\
1 & 2 & 3 & 4 & 5, 6, 7, 8, 9, 10, 11, 12, 13 \\
\ hline \ mathrm {N} & \ mathrm {O} & \ mathrm {P} & \ mathrm {Q} & \ mathrm {R } & \ mathrm {S} & \ mathrm {T} & \ mathrm {U} & \ mathrm {V} & \ mathrm {W} & \ mathrm {X} & \ mathrm {Y} & \ mathrm {Z} \ \
14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26
\ end {array} \ nonumber \]

Пример \ (\ PageIndex {1} \)

Используйте матрицу \ (A = \ left [\ begin {array} {ll}
1 & 2 \\
1 & 3
\ end {array} \ right] \) для кодирования сообщения: ATTACK NOW!

Решение

Разделяем буквы сообщения на группы по две.

\ [\ begin {array} {lllll} \ text {AT} & \ text {TA} & \ text {CK} & \ text {-N} & \ text {OW} \ end {array} \ nonumber \]

Мы присваиваем этим буквам числа из вышеприведенной таблицы и конвертируем каждую пару чисел в матрицы \ (2 \ times 1 \). В случае, когда на конце остается одна буква, добавляется пробел, чтобы превратить ее в пару.

\ [\ left [\ begin {array} {c}
\ mathrm {A} \\
\ mathrm {T}
\ end {array} \ right] = \ left [\ begin {array} {c}
1 \\
20
\ end {array} \ right] \ quad \ left [\ begin {array} {l}
\ mathrm {T} \\
\ mathrm {A}
\ end {array} \ right] = \ left [\ begin {array} {c}
20 \\
1
\ end {array} \ right] \ quad \ left [\ begin {array} {l}
\ mathrm {C} \\
\ mathrm {K}
\ end {array} \ right] = \ left [\ begin {array} {l}
3 \\
11
\ end {array} \ right] \ nonumber \]

\ [\ left [\ begin {array} {c}
— \\
\ mathrm {N}
\ end {array} \ right] = \ left [\ begin {array} {l}
27 \\
14
\ end {array} \ right] \ quad \ left [\ begin {array} {l}
\ mathrm {O} \\
\ mathrm {W}
\ end {array} \ right] = \ left [ \ begin {array} {l}
15 \\
23
\ end {array} \ right] \ nonumber \]

Итак, на данном этапе наше сообщение, выраженное в виде матриц \ (2 \ times 1 \), выглядит следующим образом.

\ [\ left [\ begin {array} {c}
1 \\
20
\ end {array} \ right] \ left [\ begin {array} {c}
20 \\
1
\ end { array} \ right] \ left [\ begin {array} {c}
3 \\
11
\ end {array} \ right] \ left [\ begin {array} {c}
27 \\
14
\ конец {массив} \ right] \ left [\ begin {array} {c}
15 \\
23
\ end {array} \ right] \ quad \ bf {(I)} \ nonumber \]

Теперь, чтобы закодировать, мы умножаем слева каждую матрицу нашего сообщения на матрицу \ (A \). Например, произведение \ (A \) на нашу первую матрицу: \ (\ left [\ begin {array} {ll}
1 & 2 \\
1 & 3
\ end {array} \ right] \ left [\ begin {array} {c}
1 \\
20
\ end {array} \ right] = \ left [\ begin {array} {l}
41 \\
61
\ end {array} \ справа] \)

И произведение \ (A \) на нашу вторую матрицу: \ (\ left [\ begin {array} {ll}
1 & 2 \\
1 & 3
\ end {array} \ right] \ left [\ begin {array} {l}
20 \\
1
\ end {array} \ right] = \ left [\ begin {array} {l}
22 \\
23
\ end {array} \ right ] \)

Умножение каждой матрицы в \ (\ bf {(I)} \) на матрицу \ (A \), в свою очередь, дает желаемое закодированное сообщение:

\ [\ left [\ begin {array} {l}
41 \\
61
\ end {array} \ right] \ left [\ begin {array} {l}
22 \\
23
\ end { array} \ right] \ left [\ begin {array} {l}
25 \\
36
\ end {array} \ right] \ left [\ begin {array} {l}
55 \\
69
\ конец {массив} \ right] \ left [\ begin {array} {l}
61 \\
84
\ end {array} \ right] \ nonumber \]

Пример \ (\ PageIndex {2} \)

Расшифруйте следующее сообщение, которое было закодировано с использованием матрицы \ (A = \ left [\ begin {array} {ll}
1 & 2 \\
1 & 3
\ end {array} \ right] \).

\ [\ left [\ begin {array} {l}
21 \\
26
\ end {array} \ right] \ left [\ begin {array} {l}
37 \\
53
\ end { array} \ right] \ left [\ begin {array} {l}
45 \\
54
\ end {array} \ right] \ left [\ begin {array} {c}
74 \\
101
\ end {array} \ right] \ left [\ begin {array} {l}
53 \\
69
\ end {array} \ right] \ quad (\ bf {II}) \]

Решение

Поскольку это сообщение было закодировано умножением на матрицу \ (A \) в примере \ (\ PageIndex {1} \), мы декодируем это сообщение, сначала умножая каждую матрицу слева на матрицу, обратную матрице \ (A \) нижеприведенный.{-1} \) получаем следующее.

\ [\ left [\ begin {array} {c}
11 \\
5
\ end {array} \ right] \ left [\ begin {array} {c}
5 \\
16
\ end { array} \ right] \ left [\ begin {array} {c}
27 \\
9
\ end {array} \ right] \ left [\ begin {array} {c}
20 \\
27
\ конец {массив} \ right] \ left [\ begin {array} {c}
21 \\
16
\ end {array} \ right] \ nonumber \]

Наконец, сопоставив числа с соответствующими буквами, мы получим:

\ [\ left [\ begin {array} {l}
\ mathrm {K} \\
\ mathrm {E}
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {E} \\
\ mathrm {P}
\ end {array} \ right] \ left [\ begin {array} {l}
— \\
\ mathrm {I}
\ end {array} \ right ] \ left [\ begin {array} {l}
\ mathrm {T} \\
—
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {U} \\
\ mathrm {P}
\ end {array} \ right] \ nonumber \]

И сообщение гласит: СОХРАНИТЕ ЭТО.

Теперь предположим, что мы хотим использовать матрицу \ (3 \ times 3 \) для кодирования сообщения, а затем вместо разделения букв на группы по два, мы разделим их на группы по три.

Пример \ (\ PageIndex {3} \)

Использование матрицы \ (B = \ left [\ begin {array} {ccc}
1 & 1 & -1 \\
1 & 0 & 1 \\
2 & 1 & 1
\ end {array} \ right ] \ nonumber \), закодируйте сообщение: АТАКА СЕЙЧАС!

Решение

Разделяем буквы сообщения на группы по три.

ATT ACK -NO W- —

Обратите внимание, что, поскольку в конце осталась единственная буква «W», мы добавили два пробела, чтобы превратить ее в тройку.

Теперь мы присваиваем числам соответствующие буквы из таблицы и конвертируем каждую тройку чисел в матрицы \ (3 \ times 1 \). Получаем

\ [\ left [\ begin {array} {l}
\ mathrm {A} \\
\ mathrm {T} \\
\ mathrm {T}
\ end {array} \ right] = \ left [\ begin {array} {c}
1 \\
20 \\
20
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {A} \\
\ mathrm {C } \\
\ mathrm {K}
\ end {array} \ right] = \ left [\ begin {array} {l}
1 \\
3 \\
11
\ end {array} \ right] \ left [\ begin {array} {l}
— \\
\ mathrm {N} \\
\ mathrm {O}
\ end {array} \ right] = \ left [\ begin {array} {l}
27 \\
14 \\
15
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {W} \\
— \\
—
\ end {array} \ right] = \ left [\ begin {array} {l}
23 \\
27 \\
27
\ end {array} \ right] \ nonumber \]

Пока у нас

\ [\ left [\ begin {array} {c}
1 \\
20 \\
20
\ end {array} \ right] \ left [\ begin {array} {c}
1 \\
3 \\
11
\ end {array} \ right] \ left [\ begin {array} {c}
27 \\
14 \\
15
\ end {array} \ right] \ left [\ begin {array } {c}
23 \\
27 \\
27
\ end {array} \ right] \ quad \ bf {(III)} \ nonumber \]

Мы умножаем слева каждую матрицу нашего сообщения на матрицу \ (B \). {- 1} \) и связываем числа с соответствующими буквами алфавита.{-1} \) для декодирования зашифрованного сообщения.

Пример \ (\ PageIndex {4} \)

Расшифруйте следующее сообщение, которое было закодировано с использованием матрицы \ (B = \ left [\ begin {array} {lll}
1 & 1 & -1 \\
1 & 0 & 1 \\
2 & 1 & 1
\ конец {массив} \ right] \).

\ [\ left [\ begin {array} {l}
11 \\
20 \\
43
\ end {array} \ right] \ left [\ begin {array} {l}
25 \\
10 \\
41
\ end {array} \ right] \ left [\ begin {array} {l}
22 \\
14 \\
41
\ end {array} \ right] \ quad \ bf {(IV )} \ nonumber \]

Решение

Так как это сообщение было закодировано умножением на матрицу \ (B \).{-1} \) дает следующее.

\ [\ left [\ begin {array} {c}
8 \\
15 \\
12
\ end {array} \ right] \ left [\ begin {array} {c}
4 \\
27 \\
6
\ end {массив} \ right] \ left [\ begin {array} {c}
9 \\
18 \\
5
\ end {array} \ right] \ nonumber \]

Наконец, сопоставив числа с соответствующими буквами, мы получим

\ [\ left [\ begin {array} {l}
\ mathrm {H} \\
\ mathrm {O} \\
\ mathrm {L}
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {D} \\
— \\
\ mathrm {F}
\ end {array} \ right] \ left [\ begin {array} {l}
\ mathrm {I} \\
\ mathrm {R} \\
\ mathrm {E}
\ end {array} \ right] \ quad \ text {Сообщение гласит:} \ mathrm {HOLD} \ text {FIRE} \ nonumber \]

Сообщение гласит: УДЕРЖАТЬ ОГОНЬ.

Суммируем:

ДЛЯ КОДИРОВАНИЯ СООБЩЕНИЯ

1. Разделите буквы сообщения на группы по две или три.

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

3. Преобразуйте каждую группу чисел в матрицы столбцов.

3. Преобразуйте эти матрицы столбцов в новый набор матриц столбцов, умножив их на совместимую квадратную матрицу по вашему выбору, имеющую обратную.Этот новый набор чисел или матриц представляет закодированное сообщение.

ДЛЯ РАСШИФРОВКИ СООБЩЕНИЯ

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

2. Свяжите числа с соответствующими буквами.

Кодирование Хаффмана

Описание в основном взято у профессора Виджая Рагхунатана. В в этом задании вы будете использовать свои знания о приоритетных очередях, стеках, и деревья для разработки программы сжатия файлов и программы распаковки файлов (похожий застегнуть и разархивировать). Вы будете основывать свои утилиты на широко используемом алгоритмическом методе Кодирование Хаффмана, которое используется при сжатии JPEG, а также в аудио MP3. сжатие.

Кодировка ASCII

Многие языки программирования используют ASCII (что означает Американский стандартный код для обмена информацией) кодирование для представления символов.В кодировке ASCII кодируется каждый символ. (представлен) с одинаковым количеством бит (8 бит) на символ. С тех пор 256 различных значений, которые могут быть представлены 8-битными, есть потенциально 256 различных символов в наборе символов ASCII, как показано на таблица символов ASCII доступна на http://www.asciitable.com/.

Давайте теперь посмотрим на простой пример кодировки символов ASCII. Используя кодировку ASCII (8 бит на символ) 13-символьный строка «иди, суслики» требует 13 * 8 = 104 бит.В таблице ниже показано, как работает кодирование.

Персонаж

ASCII код

8-бит двоичное значение

Космос

32

00100000

e

101

01100101

г

103

01100111

ч

104

01101000

или

111

01101111

п.

112

01110000

r

114

01110010

с

115

01110011

Данная строка будет будет записан как следующий поток бит (пробелы будут не записывать, только нули и единицы)

01100111 01101111 00100000 01100111 01101111 00100000 01100111 01101111 01110000 01101000 01100101 01110010 01110011

Отметим, что мы предполагаем, что для каждого байта у нас есть старший бит слева, а младший бит справа для этого PE / PA.На самом деле это не так имеет значение, за исключением того, что программы сжатия и распаковки должны следовать такой же порядок битов.

От Кодирование ASCII в сторону кодирования Хаффмана

Далее, давайте посмотрим, как мы можем используйте меньшее количество битов, используя более простую схему кодирования. Так как всего 8 разных персонажи из «Go gophers», можно использовать только 3 бита для кодирования 8 различных символов. Мы может, например, использовать кодировку, показанную в таблице ниже (имейте в виду, что также возможны другие 3-битные кодировки).

Персонаж

Код Стоимость

3-битный двоичное значение

г

0

000

или

1

001

п.

2

010

ч

3

011

e

4

100

r

5

101

с

6

110

Космос

7

111

Теперь строка «go gophers» будет закодирована. как: 000 001 111 000 001 111 000 001 010 011 100 101 110. Как видите, используя три бита на вместо восьми битов на символ, которые использует ASCII, строка «go go gophers» используется всего 39 бит вместо 104 бит.

Однако даже в этом улучшенном схема кодирования, мы использовали одинаковое количество бит для представления каждого символа, независимо от того, как часто символ появляется в нашей строке. Еще больше бит можно сохранить, если мы используем менее трех битов для кодирования таких символов, как g, o, и пространство, которое встречается часто и более трех бит для кодирования символов, таких как e, h, p, r и s, которые встречаются меньше часто в «ходят суслики». Это основная идея Хаффмана. кодирование: использовать меньшее количество бит для символов, которые встречаются чаще . Хорошо посмотрите, как это делается, используя древовидную структуру данных, в которой символы хранятся как его листовые узлы, и чьи пути от корня к листу обеспечивают последовательность битов, используемую для закодировать символы.

На пути к дереву кодирования

Использование двоичного дерева для кодирования, все символы хранятся на листьях дерева.Левый край нумеруется 0, а правый край пронумерован 1. Код для любой символ / листовой узел получается по пути от корня к листу и объединение 0 и 1-е. Конкретная структура дерева определяет кодировку любого листового узла с помощью ребра 0/1 описанная конвенция. В виде Например, дерево внизу справа дает кодировку, показанную слева.

Персонаж

Двоичный код

«

101

‘e’

1100

г

00

‘ч’

1101

‘или

01

‘п’

1110

‘r’

1111

‘s’

100

Используя эту кодировку, кодируется «go gophers» (опять же, пробелы не появятся в битовом потоке) как: 00 01 101 00 01 101 00 01 1110 1101 1100 1111100. Это всего 37 бит, на два бита меньше, чем при улучшенном кодировании, в котором каждый из 8 символов имеет 3-битную кодировку! Биты сохраняются кодированием часто встречающиеся символы, такие как ‘g’ и ‘o’ с меньшим количеством бит (здесь два бит), чем символы, которые встречаются реже, такие как ‘p’, ‘h’, ‘e’ и ‘р’.

Чтобы декодировать данный поток, который был закодирован данным деревом, начните с корня дерева и следуйте левая ветвь, если следующий бит в потоке равен 0, и правая ветвь, если следующий бит в потоке — 1.Когда дойдете до листа, напишите иероглиф хранится у листа, и снова начните с вершины дерева. Битовый поток 10011101101110011111100 дает вправо-влево-влево на букву ‘s’, затем (начиная с корня) с право-право-право-лево до буква «р», за которой следует право-право-лево-право до буквы «h». Таким образом, продолжение дает декодированную строку «сфера».

Коды префикса

Когда все персонажи хранятся в листьях, и каждый интерьер (не листовой) узел имеет двух дочерних узлов, кодирование вызвано соглашением 0/1 описанное выше удовлетворяет очень важному свойству, называемому префиксом . свойство , в котором говорится, что кодирование символа битовой последовательностью не является префикс кодирования битовой последовательности любого другого символа.Это делает это возможно декодировать поток битов с использованием дерева кодирования, следуя от корня к листу пути. Дерево, показанное выше для слова «go gophers», удовлетворяет этому префиксу. собственности и является оптимальным деревом. Есть и другие деревья, использующие 37 бит; например, вы можете просто поменять местами любой узлы-братья и получают другую кодировку, в которой используется то же количество бит. Следующий, мы рассмотрим алгоритм построения такого оптимального дерева. Этот алгоритм называется кодированием Хаффмана и было изобретено Дэвидом А. Хаффманом в 1952 году, когда он был доктором.D. студент Массачусетского технологического института.

Кодирование Хаффмана

В предыдущем разделе мы видели примеры того, как поток битов может быть сгенерирован из кодировки. Мы также увидели, как дерево можно использовать для декодирования поток битов. Здесь мы обсудим, как построить дерево, используя метод Хаффмана. алгоритм.

Предположим, что с каждым символом связан вес, который равно количеству раз, когда символ встречается в файле.Например, в строка «go gophers», символы ‘g’ и ‘o’ имеют вес 3, пробел имеет вес 2, а остальные символы имеют вес 1. Когда сжатие файла, нам нужно сначала прочитать файл и вычислить эти веса. Предположим, что все веса символов были рассчитаны. Хаффмана алгоритм предполагает, что мы строим одно дерево из группы (или леса) деревья. Изначально все деревья имеют один узел, содержащий символ и вес персонажа. Итеративно новое дерево формируется путем выбора двух деревьев. и создание нового дерева, дочерние узлы которого являются корнями двух деревьев.В Вес нового дерева — это сумма весов двух поддеревьев. Это уменьшает количество деревьев на одно на каждой итерации. Процесс повторяется до тех пор, пока не останется только одно дерево. Алгоритм следующий:

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

    Выберите два дерева с помощью наименьшие веса; назовите эти деревья T 1 и T 2 . Создать новое дерево, корень которого имеет вес, равный сумме весов T 1 + T 2 , левое поддерево которого — T 1 , а правое поддерево — T 2 .

  1. Единственное дерево, оставшееся после предыдущего шага, является оптимальным дерево кодирования.

Мы будем использовать в качестве примера строку «go gophers».Первоначально у нас есть лес, показанный ниже. Узлы показаны с весом, который представляет количество раз, когда символ узла встречается в данном вводе строка / файл.

Выбираем два минимальных узла. Есть пять узлов с минимальным вес 1. В этой реализации мы поддерживаем приоритетную очередь с предметы, расположенные по их весу. Когда у двух предметов одинаковые вес, листовой узел (т.е., узел, связанный с символом ASCII) является всегда заказывал первым. Если оба узла являются листовыми, они упорядочиваются в соответствии с к их кодировке ASCII. Если оба узла не являются листовыми, они упорядочены в соответствии со временем создания узлов. Мы всегда выбираем первые два элемента в очереди приоритета, а именно узлы для персонажей ‘е’ и ‘час’. Мы создаем новое дерево, корень которого взвешивается суммой выбранные веса. Порядок узлов в очереди приоритетов также определяет левый и правый дочерние узлы нового корня.Теперь у нас есть лес из семи деревьев, как показано здесь. Хотя вновь созданный узел имеет такой же вес как пробел, заказывается после Место в очереди с приоритетом, потому что Пробел — это символ ASCII.

Выбор первых двух (минимальных) узлов в приоритетной очереди дает Другой дерево с весом 2 как показано ниже. Теперь в лесу деревьев есть шесть деревьев, которые будут в конечном итоге построить дерево кодирования.

Снова мы должны выбрать первые два (минимальных) узла в очереди приоритетов.Низший Вес — это ‘е’-узел / дерево с весом, равным 1. Есть три дерева с весом 2; выбранный соответствует символу ASCII, потому что способа, которым мы упорядочиваем узлы в очереди приоритетов. Новое дерево имеет вес 3, и оно будет помещено последним в списке. приоритетная очередь в соответствии с нашей стратегией заказа.

Теперь есть два дерева с весом, равным 2. Они соединены. в новое дерево весом 4.Осталось четыре дерева, одно из которых вес 4 и три с весом 3.

Первые два минимальных (вес 3) дерева в очереди с приоритетом соединены в дерево, вес которого равно 6. Осталось три дерева.

Минимальные деревья имеют веса 3 и 4; они соединены в дерево весом 7.

Наконец, последние два дерева соединяются в последнее дерево, вес которого равно 13, сумме двух весов 6 и 7.Это дерево дерево, которое мы использовали для иллюстрации кодирования Хаффмана выше. Обратите внимание, что вы можете легко придумать альтернативное оптимальное дерево, используя другое стратегия упорядочивания деревьев с одинаковым весом. В этом случае битовые шаблоны для каждого символа разные, но общее количество битов, используемых для кодировать «иди, суслики» то же самое.

Теперь покажем другое дерево сжать струну «улицы каменные звезды не» оптимально.Кодировать «улицы» у нас было бы следующее биты: 1110001111011000111101010011110.

Другое дерево / стол Хаффмана Пример

Персонаж

двоичный значение

«

101

‘а’

010

‘e’

110

‘n’

1000

‘или

1001

‘r’

011

‘s’

111

‘т’

00

Важно отметить что вы не можете использовать дерево, построенное для строки «иди, суслики», чтобы декодировать потоки битов, полученные от кодирования «улицы — это не каменные звезды», так как кодирование выполняется с использованием другого дерева.

Реализация / программирование кодирования Хаффмана

В этом разделе мы увидим основные этапы программирования при реализации Кодирование Хаффмана. Реализация состоит из двух частей: программа сжатия и программа декомпрессии. Мы предположим, что это отдельные программы, но на самом деле у них много общие функции. Для этого набора упражнений / задания по программированию вы: имеют дело в основном с декомпрессией. Однако для декомпрессии у нас есть чтобы понять сжатие.

Программа сжатия

Для сжатия файла (последовательности символов) вам понадобится битовая таблица. кодировки, то есть таблица, содержащая последовательность битов, используемых для кодирования каждого символа. Эта таблица построена из дерева кодирования с использованием путей от корня к листу к генерировать битовую последовательность, кодирующую каждый символ.

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

1. Постройте дерево кодирования Хаффмана на основе количества появления каждого символа ASCII в файле. Постройте стол Хаффмана коды для всех символов ASCII, которые появляются в файле.

2. Прочтите файл для сжатия (простой файл) и обрабатывать по одному символу за раз. Для обработки каждого символа найдите бит последовательность, которая кодирует символ с помощью таблицы, построенной на предыдущем шаге и запишите эту битовую последовательность в сжатый файл.

Основная проблема здесь заключается в том, что при кодировании символа ASCII читаемый из файла, код обычно короче 8 бит. Тем не мение, большинство систем позволяют записывать в файл по байтам или 8 битам за раз. Это становится необходимо для накопления кодов для нескольких символов ASCII перед записью 8-битного символа в выходной файл.

Для сжатия струны Например, «улицы — это каменные звезды, а не звезды», мы читаем из строки по одному символу за раз.Код для ‘s’: 111, мы не можем записать в файл еще. Читаем следующий символ ‘t’, код которого 00. Опять же, мы не можем писать на выходной файл, потому что общее количество бит всего 5. Теперь мы читаем следующий символ ‘r’, код 011. Сжатие программа теперь может печатать символ битовой комбинации 11100011 в выходной файл.

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

Продолжая процесс, программа должна будет прочитать ‘eet’, комбинированный код которого «11011000», до печати 8-битный комбинированный код в выходной файл. Когда программа читает следующие три символа ‘s’, комбинированный код «111101010». Как комбинированный код имеет на единицу больше 8 бит, программа должна распечатать первые 8 бит в выходной файл и объедините оставшийся бит со следующими символами. Вы также можете встретить коды длиной более 8 бит.Вам придется разбить такие коды на 8-битные байты.

Что произойдет, когда вы дойдете до конец файла, и вы не накопили 8 бит для печати. Все, что вам нужно сделать, это набить накопленные биты достаточным количеством 0 и распечатайте его в выходной файл.

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

Заголовок Информация

Вы должны сохранить начальные информация в сжатом файле, которая будет использоваться при распаковке / распаковке программа. По сути, вы должны сохранить дерево, которое используется для сжатия исходный файл. Это потому, что программе декомпрессии нужен именно такой дерево для декодирования данных. Мы будем называть топологию информация заголовка. В начале сжатого есть три целых числа без знака:

· Общее количество символов в сжатом файл в виде 4-байтового беззнакового целого числа.

· Общее количество символов, хранящих информация заголовка, то есть топология дерева кодирования Хаффмана, как 4-байтовое целое число без знака.

· Общее количество символов в оригинале несжатый файл, как 4-байтовое целое число без знака.

После трех беззнаковых целые числа, мы храним информацию заголовка или топологию Дерево кодирования Хаффмана, а затем следует кодирование исходного текста с использованием кодов Хаффмана.Мы описали кодировку исходного текста в предыдущих разделах. Теперь мы сосредоточимся на том, как топология Дерево кодирования Хаффмана сохраняется.

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

Рассмотрим нить «иди, суслики», информация заголовка «1g1o01s1 01e1h01p1r00000», сразу за ним следует закодированный текст. Последовательный обход дерева кодирования Хаффмана дает нам «1g1o01s1 01e1h01p1r0000». Еще один «0» отделяет топология из закодированного текста.

Для строки «улицы каменные звезды not «, информация заголовка «1t1a1r001n1o01 01e1s0000», а затем по закодированному тексту.

В этих двух примерах мы используем символы 0 и 1 к различать нелистовые и листовые узлы (и 0 для обозначения конец топологии).Поскольку в каждом из двух примеров, есть восемь единиц, семь нулей для нелистовых узлов, и еще один 0, чтобы указать, что мы достигли конца топологии. Этот подход использовал в общей сложности 24 байта.

Информацию заголовка можно сделать более экономичной, если использовать биты 0 и 1 к различать нелистовые и листовые узлы, а также указывать конец топологии. В этих двух примерах всего будет 10 байтов (8 байтов для листовых узлов и 2 байта для всех 0 и Единицы).Проблема здесь в том, что как программы сжатия, так и программы распаковки придется обрабатывать биты вместо символов. Например, в битовой подход, первые 16 бит (или первые 2 байта) информации заголовка для кодирования строка «улицы каменные звезды» не являются 10111010 01011000 (обратите внимание, что пространство в битовом потоке введено для большей ясности). Кодировка ASCII для ‘t’ охватывает два байта, 7 бит в первом байте и 1 бит во втором байте. Второй по величине значащий бит во втором байт равен 1, указывает, что следующие 8 бит являются символом ASCII, из которых 6 старших разрядов символа ‘а’ содержится в наименьшем значащие 6 бит второго байта.

В битовом представлении дерева кодирования Хаффмана последний байт не может содержать 8 бит. В этом случае мы снова заполняем его с 0 битами. Рассмотрим случай где входной файл использует девять различных символов ASCII. Номер битов, необходимых для представления дерева кодирования Хаффмана, составляет 9 × 8 + 9 × 2 = 90 бит, которые могут быть представлены 12 байтами. Другими словами, последний байт должен содержать только два полезных бита. За 12 байтами следует закодированный текст.

Программа декомпрессии или удаления воздуха

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

1. Постройте дерево кодирования Хаффмана на основе заголовка Информация. Вероятно, вам понадобится второе целое число без знака, хранящееся в начало сжатого файла, чтобы помочь с построением.

2. Читать по битам из сжатого файла (начиная с места после информации заголовка). Используйте чтение бит для обхода дерева кодирования Хаффмана (0 для левого и 1 для правого), начиная с корневого узла. Когда программа достигнет листового узла, распечатайте соответствующий символ ASCII выходному файлу.Начинается с корневой узел дерева кодирования Хаффмана при чтении следующего бита. Программа завершается, когда количество декодированных символов совпадает с количество символов, хранящихся как третье целое число без знака в начале сжатый файл.

Чтобы построить дерево кодирования Хаффмана из информации заголовка, мы делаем использование стека. Когда 1 (бит или характер в зависимости от того, имеем ли мы дело с битовой или символьное представление) читаем, читаем следующий байт и нажимаем соответствующий символ ASCII в стек.Когда 0 (бит или символ) читается, если стек содержит только один элемент, мы имеем построил все дерево кодирования Хаффмана. В противном случае должно быть больше чем один элемент в стеке. Мы создаем новый узел и выталкиваем верх два элемента из стека. Мы делаем первый элемент из стека правый дочерний элемент нового узла и второй элемент вне стека левый дочерний элемент нового узла. После этого нажимаем только что созданный узел в стек.

Проблема заключается в чтении бита из сжатого файла.Очередной раз, чтение из файла происходит на байтовом уровне. В программе декомпрессии вам нужно прочитать 8-битный символ ASCII, который охватывает два байта в сжатый файл, если вы хотите построить дерево кодирования Хаффмана. Вы также должны читать по одному бит за раз, чтобы определить, являетесь ли вы работа с листовым узлом или неклистовым узлом. Конечно, вы также должны читать по одному биту, когда вы хотите декодировать сжатый файл. Стратегия состоит в том, чтобы всегда читать байт из сжатого файла.Вы тоже поддерживать индекс, чтобы указать, где вы находитесь в этом байте. Например, когда вы читаете символ, индекс должен указывать на наиболее значимые бит (т. е. 7-й бит, предполагая, что младший значащий бит 0-й бит). После того, как вы обработали один бит, индекс должен быть уменьшен на 1.

Практических вопросов по кодированию Хаффмана

Кодирование Хаффмана — важная тема с точки зрения GATE, и в этой теме задаются различные типы вопросов.Прежде чем разбираться в этой статье, вы должны иметь общее представление о кодировке Хаффмана.

Это типы вопросов, которые задаются в GATE на основе кодирования Хаффмана.

Тип 1. Концептуальные вопросы, основанные на кодировании Хаффмана —
Вот несколько ключевых моментов, основанных на кодировании Хаффмана:

  • Это метод сжатия данных без потерь, генерирующий коды переменной длины для различных символов.
  • Он основан на жадном подходе, который учитывает частоту / вероятность алфавитов для генерации кодов.
  • Имеет сложность nlogn, где n — количество уникальных символов.
  • Длина кода символа обратно пропорциональна частоте его появления.
  • Нет кода — это префикс другого кода, благодаря которому последовательность кода может быть однозначно декодирована в символы.

Que — 1. Что из следующего верно о кодировании Хаффмана?
(A) Кодирование Хаффмана в некоторых случаях может приводить к потерям.
(B) Коды Хаффмана могут не быть оптимальными кодами без потерь в некоторых случаях.
(C) При кодировании Хаффмана никакой код не является префиксом любого другого кода.
(D) Все вышеперечисленное

Решение: Как уже говорилось, кодирование Хаффмана — это метод сжатия без потерь. Следовательно, варианты (A) и (B) неверны. Вариант (C) верен, так как это основа декодирования сообщения по заданному коду.


Тип 2. Чтобы найти количество битов для кодирования данного сообщения —
Чтобы решить этот тип вопросов:

  • Сначала вычислите частоту символов, если не задано
  • Сгенерируйте дерево Хаффмана
  • Рассчитайте количество бит, используя частота символов и количество битов, необходимых для представления этих символов.

Que — 2. Сколько битов может потребоваться для кодирования сообщения «mississippi»?

Решение: Ниже приводится таблица частот символов в ‘mississippi’ в неубывающем порядке частоты:

Сгенерированное дерево Хаффмана:

Ниже приведены коды:

Общее количество битов
= частота (м) * длина кода (м) + частота (p) * длина_кода (p) + частота (с) * длина_кода (с) + частота (i) * длина кода (i)
= 1 * 3 + 2 * 3 + 4 * 2 + 4 * 1 = 21

Кроме того, среднее количество бит на символ можно найти как:
Общее количество требуемых битов / общее количество символов = 21/11 = 1.909

Тип 3. Расшифровка кода в сообщение —
Для решения этого типа вопроса:

  • Сгенерируйте коды для каждого символа, используя дерево Хаффмана (если не указано)
  • Используя сопоставление префиксов, замените коды символами.

Que — 3. Символы от a до h имеют следующий набор частот, основанный на первых 8 числах Фибоначчи:

a: 1, b: 1, c: 2, d: 3, e: 5, f: 8, g: 13, h: 21

Код Хаффмана используется для представления символов.Какая последовательность символов соответствует следующему коду?


110111100111010

(A) fdheg
(B) ecgdf
(C) dchfg
(D) fehdg

Решение: Используя частоты, указанные в вопросе, дерево Хаффмана можно сгенерировать как:

Ниже приведены коды:

Используя сопоставление префиксов, данная строка может быть разложена на

110 11110 0 1110 10
f d h e g

Тип 4.Число битов, сохраненных с использованием кодирования Хаффмана —

Que — 4. Сетевая компания использует метод сжатия для кодирования сообщения перед передачей по сети. Предположим, что сообщение содержит следующие символы с указанием их частоты:

Обратите внимание, что каждый символ во входном сообщении занимает 1 байт.

Если используется метод сжатия кодирования Хаффмана, сколько битов будет сохранено в сообщении?
(A) 224
(B) 800
(C) 576
(D) 324

Решения: Определение количества бит без использования Хаффмана,
Общее количество символов = сумма частот = 100
размер 1 символа = 1 байт = 8 бит
Общее количество бит = 8 * 100 = 800

Используя кодирование Хаффмана, общее количество необходимых битов можно рассчитать как:

5 * 4 + 9 * 4 + 12 * 3 + 13 * 3 + 16 * 3 + 45 * 1 = 224

Сохраненные биты = 800-224 = 576.

Выбор и применение кодировки символов

Выбор и применение кодировки символов

Целевая аудитория: Кодировщики HTML (использующие редакторы или сценарии), разработчики сценариев (PHP, JSP и т. Д.), Кодировщики CSS, менеджеры веб-проектов и все, кто плохо знаком с кодировками символов и нуждается в введении в то, как выбирать и применять кодировки символов.

Какую кодировку символов я должен использовать для своего контента и как применить ее к моему контенту?

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

Эта статья предлагает простые советы о том, какую кодировку символов использовать для вашего контента и как ее применять, т. Е.как на самом деле создать документ в этой кодировке.

Если вам нужно лучше понять, что такое символы и кодировки символов, см. Статью Кодировки символов для начинающих .

Выберите UTF-8 для всего содержимого и подумайте о преобразовании любого содержимого из устаревших кодировок в UTF-8.

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

Проверьте, повлияют ли на ваш выбор настройки HTTP-сервера.

Помимо объявления кодировки документа внутри документа и / или на сервере, вам необходимо сохранить текст в этой кодировке, чтобы применить его к вашему контенту.

Разработчикам также необходимо убедиться, что различные части системы могут взаимодействовать друг с другом.

Применение кодировки к вашему контенту

Авторы контента должны объявить кодировку символов своих страниц, используя один из методов, описанных в Объявление кодировок символов в HTML .

Однако важно понимать, что простое объявление кодировки внутри документа или на сервере фактически не изменит байты; вам нужно сохранить текст в этой кодировке , чтобы применить его к вашему контенту. (Объявление просто помогает браузеру интерпретировать последовательности байтов, в которых хранится текст.)

В статье Установка кодировки в приложениях веб-разработки даются советы о том, как установить кодировку страницы при ее сохранении для ряда сред редактирования.

По возможности установите UTF-8 по умолчанию для новых документов в редакторе. На рисунке ниже показано, как это сделать в настройках редактора, такого как Dreamweaver.

Для получения информации о «Форме нормализации Unicode» см. Нормализация в HTML и CSS . Для получения информации о «Unicode Signature (BOM)» см. The byte-order mark (BOM) в HTML .

Вам также может потребоваться проверить, что ваш сервер обслуживает документы с правильными декларациями HTTP, поскольку в противном случае он переопределит информацию в документе (см. Ниже).

Разработчикам также необходимо убедиться, что различные части системы могут взаимодействовать друг с другом. Веб-страницы должны иметь возможность беспрепятственно взаимодействовать с серверными скриптами, базами данных и т. Д. Все они, конечно, лучше всего работают и с UTF-8. Разработчики могут найти подробный набор вещей, которые следует учитывать в статье Переход на Unicode .

Зачем использовать UTF-8?

HTML-страница может быть только в одной кодировке. Вы не можете кодировать разные части документа в разных кодировках.

Кодировка на основе Unicode, такая как UTF-8, может поддерживать множество языков и может размещать страницы и формы на любом сочетании этих языков. Его использование также устраняет необходимость в логике на стороне сервера для индивидуального определения кодировки символов для каждой обслуживаемой страницы или каждой входящей отправки формы. Это значительно упрощает работу с многоязычным сайтом или приложением.

Кодировка Unicode также позволяет смешивать на одной странице намного больше языков, чем любой другой выбор кодировки.

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

В наши дни барьеры для использования Unicode очень низки. Фактически, в январе 2012 года Google сообщил, что более 60% Интернета в их выборке из нескольких миллиардов страниц теперь используют UTF-8.Добавьте к этому цифру для веб-страниц, содержащих только ASCII (поскольку ASCII является подмножеством UTF-8), и эта цифра возрастет примерно до 80%.

Существует три различных кодировки символов Unicode: UTF-8, UTF-16 и UTF-32. Из этих трех только UTF-8 следует использовать для веб-содержимого. Спецификация HTML5 гласит: «Авторам рекомендуется использовать UTF-8. Средства проверки соответствия могут рекомендовать авторам не использовать устаревшие кодировки. Инструменты разработки должны по умолчанию использовать UTF-8 для вновь создаваемых документов».

Обратите внимание, в частности, что все символы ASCII в UTF-8 используют в точности те же байты, что и кодировка ASCII, что часто способствует совместимости и обратной совместимости.

Принимая во внимание HTTP-заголовок

Любое объявление кодировки символов в заголовке HTTP переопределит объявления внутри страницы. Если заголовок HTTP объявляет кодировку, отличную от той, которую вы хотите использовать для своего контента, это вызовет проблему, если вы не сможете изменить настройки сервера.

У вас может не быть контроля над объявлениями, которые идут с заголовком HTTP, и вам, возможно, придется обратиться за помощью к людям, которые управляют сервером.С другой стороны, иногда есть способы исправить что-то на сервере, если у вас ограниченный доступ к файлам настройки сервера или если вы создаете страницы с использованием языков сценариев. Например, см. Установка параметра кодировки HTTP для получения дополнительной информации о том, как изменить информацию о кодировке либо локально для набора файлов на сервере, либо для контента, созданного с использованием языка сценариев.

Обычно перед этим необходимо проверить, действительно ли заголовок HTTP объявляет кодировку символов.Вы можете использовать средство проверки интернационализации W3C, чтобы узнать, какая кодировка символов, если таковая имеется, указана в заголовке HTTP. В качестве альтернативы, статья Проверка заголовков HTTP указывает на некоторые другие инструменты для проверки информации о кодировке, передаваемой сервером.

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

Что делать, если я не могу использовать UTF-8?

Если вы действительно не можете избежать использования кодировки символов, отличной от UTF-8, вам нужно будет выбрать из ограниченного набора имен кодировки, чтобы обеспечить максимальную совместимость и максимально долгий срок читабельности вашего контента, а также минимизировать уязвимости безопасности.

До недавнего времени реестр IANA был местом, где можно было найти имена для кодировок. Реестр IANA обычно включает несколько имен для одной и той же кодировки. В этом случае вы должны использовать имя, обозначенное как «предпочтительный».

Новая спецификация Encoding теперь предоставляет список, который был протестирован на реальных реализациях браузеров. Вы можете найти список в таблице в разделе «Кодировки». Лучше всего использовать имена из левого столбца этой таблицы.

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

Избегайте этих кодировок

Спецификация HTML5 называет ряд кодировок, которых следует избегать.

Документы не должны использовать JIS_C6226-1983 , JIS_X0212-1990 , HZ-GB-2312 , JOHAB (кодовая страница Windows 1361), кодировки на основе ISO-2022 или кодировки на основе CD .Это связано с тем, что они позволяют кодовым точкам ASCII представлять символы, отличные от ASCII, что представляет собой угрозу безопасности.

Документы

также не должны использовать кодировки CESU-8 , UTF-7 , BOCU-1 или SCSU , поскольку они никогда не предназначались для веб-содержимого, а спецификация HTML5 запрещает браузерам их распознавать.

Спецификация также настоятельно не рекомендует использовать UTF-16 , а использование UTF-32 «особенно не рекомендуется».

Также следует избегать других кодировок символов, перечисленных в спецификации Encoding . К ним относятся кодировки Big5 и EUC-JP , которые имеют проблемы совместимости. ISO-8859-8 (кодировка на иврите для визуально упорядоченного текста) также следует избегать в пользу кодировки, которая работает с логически упорядоченным текстом (например, UTF-8 или в противном случае ISO-8859-8-i).

Кодировка , заменяющая кодировку , указанная в спецификации Encoding , на самом деле не является кодировкой; это резервный вариант, который отображает каждый октет в кодовую точку Unicode U + FFFD REPLACEMENT CHARACTER.Очевидно, что передавать данные в такой кодировке бесполезно.

Определяемая пользователем кодировка x — это однобайтовая кодировка, нижняя половина которой — ASCII, а верхняя половина отображается в область частного использования Unicode (PUA). Как и PUA в целом, лучше избегать использования этой кодировки в общедоступном Интернете, поскольку она наносит ущерб совместимости и долгосрочному использованию.

.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *