Универсальность двоичного кодирования

тема этого урока универсальность двоичного кодирования равномерное и неравномерное коды на прошлом уроке мы узнали что для удобства хранения и передачи информации и и часто переводят из непрерывной формы в дискретную такой процесс называется дискретизации в процессе дискретизации информация записывается на одном из языков алфавитом языка называют все существующие символы которые используются для представления информации на этом языке алфавит характеризуется своей мощностью это количество символов которые в него входят двоичный алфавит состоит из двух символов запись информации с помощью такого алфавита называется двоичным кодированием двоичный код это кот информации получившийся в результате ее двоичного кодирования также мы узнали что любой алфавит можно привести к двоичному сегодня мы узнаем как происходит двоичное кодирование звука и изображения что такое равномерный и неравномерной коды еще мы изучим двоичное кодирование текстовых сообщений методом хоффмана итак на прошлом уроке мы узнали что любой алфавит можно представить в виде двоичного для этого каждому символу исходному алфавита присваивается его двоичный код записывая подряд двоичные коды всех символов мы можем кодировать текстовые сообщения еще мы узнали что двоичный алфавит легко реализовать технически с помощью наличия или отсутствия электрического сигнала на некотором участке электрической цепи именно поэтому любая информация на компьютере представлена в виде двоичного кода однако мы знаем что на компьютере может храниться любая информация они только текстовая или числовая как же ее представить в виде двоичного кода например звук и изображение как мы знаем они представляются в виде непрерывных сигналов разберем как же представить эти два вида информации в дискретной форме начнём с изображения вполне логично что любое изображение можно разделить на некоторые участки каждый из которых имеет свой цвет именно так происходит при представлении изображений на компьютере изображение разбивается на маленькие фрагменты которые можно назвать точками каждое изображение имеет свое разрешение оно состоит из двух цифр которые разделяются крестиком или двоеточие число слева означает на сколько точек делится изображения по горизонтали а справа насколько по вертикали таким образом изображение на компьютере представляется в виде последовательности точек каждый из которых имеет свой цвет то есть изображения на компьютере можно представить последовательно записав цвета всех точек которые в него входят но как же представить цвет в виде двоичных кодов любой цвет на мониторе компьютера изображается смешиванием в разных количествах трёх основных цветов красного зеленого и синего такое представление цветов называется их art baby моделью по первым буквам названий основных цветов на английском языке то есть red green ебну так как остальные цвета это смеси трёх основных цветов в разных количествах их можно представить в виде трех чисел количеств основных цветов эти числа можно заменить двоичными кодами одинаковые разрядности записав эти коды последовательно мы получим двоичный код цвета точки таким образом изображение на компьютере представляется в виде списка двоичных кодов одинаковые разрядности каждый из которых обозначает цвет одной из точек изображения немного иначе происходит двоичное кодирование звука позже из курса физики вы узнаете что любой звук можно представить в виде непрерывной волны эту волну можно описать зависимостью и и амплитуды то есть громкости звука от времени такую зависимость легко изобразить в виде графика чтобы представить звук в виде дискретных сигналов время в течение которого продолжается звук делится на равные небольшие промежутки и на каждом из промежутков заново определяется амплитуда волны то есть громкость звука то есть звук можно представить в виде списка чисел каждый из которых означает амплитуду волны в течение небольшого промежутка времени эти числа можно представить в виде двоичных кодов с одинаковым количеством разрядов таким образом звук на компьютере представляется в виде списка двоичных кодов одинаковые разрядности каждый из которых обозначает амплитуду звуковой волны на некотором небольшом промежутке времени мы знаем что с помощью двоичного кодирования в виде последовательностей единиц и нулей можно представить любую информацию на естественном или формальном языке в том числе изображение и звук то есть информацию любой формы можно представить в виде двоичного кода что означает универсальность двоичного кодирования это и есть его главное преимущество главный недостаток двоичного кодирования это большой размер двоичного кода так при кодировании текстового сообщения одному символу текста может соответствовать несколько символов двоичного кода давайте подумаем как можно уменьшить размер двоичного кода и вообще любого кода до этого все двоичные коды которые мы рассматривали были равномерными равномерным называется код который состоит из равных по количеству разрядов кодовых комбинаций так например при кодировании алфавита для каждой буквы мы использовали двоичные коды с одинаковым количеством разрядов однако не все символы алфавита в текстовом сообщении встречаются одинаково часто поэтому для того чтобы сократить длину двоичного кода мы можем присвоить разным сигналом коды разной длины коды с меньше разрядностью можно присвоить сигналом которые сообщения встречаются чаще а коды с большей разрядностью сигналом которые встречаются в сообщении реже такой код называется неравномерным то есть он состоит из комбинаций разной длины пример неравномерного кода азбука морзе в ней разным буквам алфавита соответствует разное количество сигналов длинных и коротких например русская буква а обозначается всего двумя сигналами одним коротким и одним длинным а ъ кодируются питью сигналами двумя длинными одним коротким и двумя длинными рассмотрим один из методов неравномерного кодирования текстовых сообщений он называется методом хоффмана посмотрим как работает этот метод закодировал с его помощью сообщения мама мыла раму сначала выпишем все символы алфавита которые используются в сообщении в данном сообщении используются символы м.а. пробел л.р. и у затем нужно записать как часто в сообщении встречается каждый из символов буквы м и а повторяются по четыре раза пробел повторяется дважды буквы и л.р. и у в сообщении встречаются по одному разу затем символы сообщения записываются в порядке убывания частоты появления у нас они так и записаны теперь строится дерево частоты появления символов в сообщении в начале берутся два символа которые встречаются в сообщении реже всех у нас таких символов 4 возьмем два правых буквы r и у соединяем их линий и складываем их частоту появления в сообщении один плюс один равно двум теперь повторим то же действие реже всех у нас появлялись буквы был соединим их линиями сложив частоту появления получим 2 теперь снова смотрим где у нас самая маленькая частота появления таких частот у нас три пробел появляется дважды двум равны общее частоты появления символов и и л и символов р и у возьмем две правые чистоты и объединим их их суммарная частота равна 4 снова ищем минимальные частоты появления возьмем две правые чистоты и объединим их их сумма равна 6 теперь объединим две левые чистоты их сумма равна 8 объединим две оставшиеся чистоты их сумма равна 14 именно 14 равна длина кодируем ago сообщения теперь двигаясь сверху вниз присвоим ветвям дерева значение нулей и единиц по следующим правилам ветви с большей частотой будем присваивать единицу а ветви с меньшей частотой 0 так левой ветви верхнего узла присвоим единицу а правый 0 затем рассмотрим левый узел там две частоты равны поэтому левой ветви присвоим 0 оправой единицу рассмотрим узел частота которого равна 6 частота появления пробела меньше суммарной частоты правой ветви поэтому левой ветви присвоим 0 а правой ветви единицу по такому же принципу пронумеруем оставшиеся ветви дерева теперь двигаясь по получившемуся дереву сверху вниз мы можем записать двоичный код каждого символа так у буквы м будет код 10 у буквы а 11 у пробела два нуля и так далее теперь нам остается лишь заменить все символы в сообщении их двоичными кодами в итоге двоичный код нашего сообщения будет таким всего в нем 36 разрядов у некоторых из вас может возникнуть вопрос а как же расшифровать данное сообщение ведь в отличие от равномерного кода мы не знаем точно сколько разрядов занимает каждый символ при неравномерном кодирование достаточно чтобы кот никакого и символов не начинался skoda другого символа давайте попробуем расшифровать первые символы нашего сообщения итак сообщение начинается с единицы с единицы у нас начинаются двоичные коды букв m&a посмотрев на следующий символ 0 мы можем точно определить что первый символ это буква м по такому же принципу мы можем определить что следующий символ буква а и до конца расшифровать слово мама следующая цифра 0 с нуля у нас начинаются коды 5 символов после него идет также 0 с двух нулей у нас начинается код пробела далее идет буква м следующая цифра 0 с нуля у нас начинаются коды 5 символов возьмем следующую цифру с нуля и единицы начинаются коды четырех символов следующая цифра 0 с нуля единицы и нуля начинаются коды двух символов следующий символ снова 0 и мы можем однозначно определить что это буква и также расшифровывается и остальное сообщение давайте посмотрим двоичный код из скольких разрядов получился бы при использовании равномерного двоичного кодирования как мы помним сообщение записано с помощью алфавита мощностью 7 символов определим разрядность двоичного кода необходимую для кодирования одного символа такого алфавита как мы помним для этого необходимо определить в какую степень возвести цифру 2 чтобы получить 7 но цифру 7 мы так получить не можем поэтому результат необходимо округлить в большую сторону мы можем так получить 8 для этого двойку нужно возвести в третью степень то есть для кодирования одного символа нам потребуется 3 разрядный двоичный код определим какой код потребуется для кодирования всего сообщения для этого нужно разрядность кода одного символа то есть 3 умножить на длину всего сообщения то есть 14 символов 3 умноженное на 14 равно 42 то есть при кодировании сообщения нам потребовался бы 42 разрядный равномерный двоичный код при использовании неравномерного кода нам потребовалось всего 36 разрядов то есть на 6 разрядов меньше сокращение длины двоичного кода заметно даже при небольшой длине сообщения если длина сообщения будет больше например десятки тысяч символов разница между длинными равномерного и неравномерного кода тоже увеличится когда длина двоичного кода составляет миллиарды разрядов разница между равномерным и неравномерным кодом просто огромна сегодня мы рассмотрели универсальность двоичного кодирования равномерное и неравномерное коды мы узнали что универсальность двоичного кодирования означает что его можно применять для кодирования информации на любом формальном или не формальном языке а также изображений и звука выяснили что все коды можно разделить на равномерное и неравномерное где равномерный код состоит из комбинации равной длины а неравномерный код состоит из комбинаций разной длины опытным путем мы подтвердили что использование неравномерного кодирования позволяет сократить длину кода