Содержание:

Готовлю школьников и студентов гарантированно на 100 баллов из 100 возможных!

Здравствуйте! Меня зовут Александр Георгиевич. Я являюсь профессиональным репетитором в области информационных технологий, математике, баз данных и программирования.

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

Чтобы гарантированно набрать на официальном экзамене ОГЭ или ЕГЭ по информатике высоченный балл берите сотовый телефон, дозванивайтесь до меня и задавайте любые интересующие вопросы.

Несмотря на то, что вы являетесь чрезвычайно занятым человеком, я все-таки настаиваю на том, чтобы вы уделили $2-3$ минуты и ознакомились с отзывами клиентов, которые прошли подготовку под моим началом и добились ошеломительных результатов.

Также своим потенциальным клиентам я предлагаю на выбор $4$ различных территориальных формата, в которых могут проходить наши эффективные занятия:

Рекомендую использовать формат дистанционного обучения! Это выгодно, удобно и эффективно!

Что такое равномерный код и в каких случаях его применяют?

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

Но ваш соратник без особых проблем сможет провести дешифрацию вашего информационного сообщения, так как вы ему расскажете об алгоритме шифрации/дешифрации.

Чтобы провести кодирование вашего русскоязычного сообщения, необходимо воспользоваться равномерным кодом. В первую очередь нам необходимо вспомнить количество букв в русском алфавите – их $33$. Во вторую – необходимо воспользоваться формулой Хартли, чтобы определить количество бит, необходимых для кодирования одного символа.

Итак, давайте посчитаем, сколько требуется бит информации для кодирования одного символа из русского алфавита: $2^i >= 33$.

Поскольку $i$ – минимальное натуральное число, то $i = 6$. Делаем вывод, что для кодирования нашего сообщения нам требуется равномерный код длиной в $6$ бит. Приведу пример кодирования равномерным кодом первых и последних двух символов русскоязычного алфавита:

Символ

Равномерный код

Десятичное представление

Равномерный код – такой код, когда все символы какого-либо алфавита кодируются кодами одинаковой длины.

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

Что такое неравномерный код и в каких случаях его применяют?

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

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

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

Неравномерный код – такой код, когда все элементы какого-либо множества кодируются кодом различной длины.

Давайте попробуем закодировать неравномерным кодом часть товаров, находящихся на вашем товарном складе. Предположим, что на вашем складе размещается около $3\ 000$ различных товаров, но наиболее ходовыми являются хлеб, соль, молоко и сахар.

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

Хлеб — 00

Соль — 01

Молоко — 10

Сахар — 11

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

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

Мука — 001

Перец — 010

То есть мы выделяем на их кодирование уже по $3$ бита информации.

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

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

Равномерный код vs неравномерный код

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

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

Я хочу записаться к вам на индивидуальный урок по информатике и ИКТ

Если у вас остались какие-либо вопросы по рассматриваемой теме, то записывайтесь ко мне на первый пробный урок. Я репетитор-практик, следовательно, на своих уроках я уделяю максимум внимания решению заданий. Из теории лишь записываются самые базовые сведения: определения, тезисы, формулировки теорем и аксиом.

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

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

Для кодирования последовательности, состоящей из букв слова ШKOЛKOВО решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Ш использовали кодовое слово 00, для буквы К — 1. Укажите, какова наименьшая длина всех символов заданного слова.

Построим дерево для решения задачи. Для букв Ш и К есть кодовые слова 00 и 1 соответственно. В слове ШКОЛКОВО самая частовстречаемая буква — О, следовательно, её нужно закодировать минимальновозможным количеством символов.

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

Буквы Л и В встречаются всего один раз, закодируем их минимально возможным количеством символов.

Самая маленькая длина кодовых слов для них \(=4\) : 0110 и 0111.

Посчитаем сумму длин кодовых слов:

Ш, Л и В встречаются один раз,

Для кодирования последовательности, состоящей из букв слова Р, Б, О, Т, А используется неравномерный двоичный код, удовлетворяющий прямому условию Фано.

Вот этот код: А – 0; Р – 100; Б – 1010; О – 111; Т – 110. Необходимо сократить для одной из букв длину кодового слова так, чтобы код можно было однозначно декодировать.

Для какой буквы это возможно сделать? В ответе укажите эту букву.

Так как код удовлетворяет прямому условию Фано (ни одно кодовое слово не является началом другого), то следует учитывать это при сокращении исходных кодовых слов.

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

2. Р сократить нельзя,так как при сокращении до 10 код перестанет удовлетворять прямому условию Фано.

3. Б возможно сократить до 101, в таком случае код по-прежнему будет удовлетворять одному из условий Фано (прямому).

4. О нельзя сократить, т.к. в этом случае нарушится прямое условие Фано.

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

По каналу связи передаются сообщения, которые содержат только следующие буквы: С, Т, Р, И, М; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв С, Т, Р используются такие кодовые слова: С – 0; Т – 110; Р – 101. Укажите кратчайшее кодовое слово для буквы И, при котором код будет допускать однозначную расшифровку. Если таких кодов несколько, укажите код с наименьшим числовым значением.

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

Первый вариант: 111

Второй вариант: 100

Оба варианта удовлетворяют условию Фано (не являются началом других кодовых слов), нам подходит вариант с наименьшим значением, то есть 100 — ответ.

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

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

Для неравномерного кодирования используется условие Фано: никакой код не должен быть началом другого кода. Если выполняется это условие, то гарантируется, что закодированное сообщение можно однозначно декодировать с начала.

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

Для решения задач, связанных с подбором неравномерных двоичных кодов удобно пользоваться наглядным способом — построением дерева Фано. Дерево строится по следующим правилам. Дерево строится начиная с начального узла — сверху вниз. Из любого узла, которое не закачивается сопоставленым символом выходят две ветви: левая, соответствующая нулю и правая, соответствующая единице. Код каждого символа получается записью нулей и единиц по кратчайшему пути с верхнего узла к с соответствующему символу.

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

Решение: Строим дерево Фано.

Так как буква А встречается чаще всего, чтобы код был наименьшей длины, ветвь 0 из вершины сразу завершаем этой буквой. Из узла ветви 1 строим ветви 0 и 1, которые завершаем буквами Б и В.

Записываем получившиеся коды: А — 0, Б — 10, В — 11

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

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

В современных системах широкое распространение получила шестнадцатиразрядная кодировка Unicode. Младшие 128 кодов в этой кодировке соотвествуют таблице ASCII, а остальные коды предзначены для кодирования символов национальных языков.

Кодирование изображения

Возьмем к примеру небольшое черно-белое изображение:

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

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

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

В современных компьютерных системах для пикселя отводят 3 байта, один байт для каждого из основных цветов: красного, зеленого и синего. То есть 24 бита обеспечивают представление 2 24 = 16 777 216 цветов.

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

Задача: Какой объем видеопамяти в байтах требуется для хранения растрового изображения, занимающего весь экран монитора с разрешающей способностью 640?480 пикселей, если используется палитра из 65536 цветов?

Решение: Глубина цвета составляет log265536 = 16 бит. Следовательно для хранения одно пикселя требуется 2 байта. Объем видеопамяти: 640 ? 480 ? 2 = 614400 байт.

Кодирование звуковой информации

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

Частота, с которой производится измерение сигнала, называется частотой дискретизации. Для качественного кодирования по теореме Найквиста эта частота должна быть в два раза выше частоты кодируемого сигнала. Так как человек слышит звук частотой до 20 кГц, то достаточно кодировать его частотой свыше 40 кГц. К примеру, на компакт-дисках применяется частота дискретизации 44 кГц, а для человеческого голоса при кодировании для передачи по каналам связи достаточно 8 кГЦ.

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

Итак, частота дискретизации при кодировании означает количество отсчетов в секунду. Частота 44 кГц — это 44000 отсчетов в секунду. Чтобы вычислить объем информации в битах, необходимый для кодирования звукового сигнала нужно частоту дискретизации умножить на глубину кодирования и на количество секунд, в течении которого сигнал кодируется. Если каналов звукового сигнала больше чем один, то полученный объем надо умножить еще и на количество каналов, например, на 2 при стерео-звуке.

Задача: Сколько байтов требуется для кодирования 1 минуты речи с частотой дискретизации 8 кГц и глубиной кодирования 10 бит.

Решение: Так как в минуте 60 секунд, то требуемый объем 8000 ? 60 ? 10 = 4800000 бит. Делим на 8, получаем 600000 байтов.

Скорость передачи информации

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

Зная пропускную способность канала можно вычислить объем передаваемой информации за какое-то время.

Задача: Скорость передачи данных (пропускная способность) через ADSL-соединение равна 64000 бит/c. Передача файла через это соединение заняла 30 секунд. Определить размер файла в байтах.

Решение: 640000 ? 30 = 1920000 бит. переведем в байты, 1920000 : 8 = 240000 байт.

Равномерные и неравномерные двоичные коды. Условие Фано

Кодирование символов обычно предполагает, что каждому символу всегда сопоставляется одинаковое количество битов (например, в кодовой таблице ASCII каждому символу сопоставляется один байт, хранящий порядковый номер того или иного символа в этой таблице). Такой способ кодирования прост и удобен, однако очевидно, что он является не самым оптимальным. Для значительной части символов используются не все биты отведенных под них байтов (часть старших битов — нулевые), а при наличии в тексте только части символов, предусмотренных в таблице ASCII (например, если текст содержит только прописные русские буквы), приходится все равно использовать 8-битный код.

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

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

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

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

Для однозначности декодирования последовательности кодов достаточно выполнения хотя бы одного из двух вышеуказанных условий Фано:

— при выполнении прямого условия Фано последовательность кодов однозначно декодируется с начала;

— при выполнении обратного условия Фано последовательность кодов однозначно декодируется с конца.

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

Вместе с тем нужно помнить, что правила Фано — это достаточное, но не необходимое условие однозначного декодирования: если не выполняется ни прямое, ни обратное правило Фано, конкретная двоичная последовательность может оказаться такой, что она декодируется однозначно (так как остальные возможные варианты до конца декодирования довести не удаётся). В подобном случае необходимо пытаться строить дерево декодирования в обоих направлениях.

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

Если для заданной последовательности кодов выполняется прямое правило Фано, то её декодирование необходимо вести с начала (слева направо).

Если для заданной последовательности кодов выполняется обратное правило Фано, то её декодирование необходимо вести с конца (справа налево).

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

Разбор типовых задач

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А-1, Б-000, В-001, Г-011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

Как неравномерный двоичный код