Двоичное кодирование. Мощность алфавита и длина кода

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

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

Два знака и два разных алфавита

Двоичный алфавит содержит два символа: 0 и 1. Исходный алфавит может содержать пять значков, шесть команд или много букв. Не смешивай его мощность N с числом знаков, которыми записывают код. При равномерном кодировании каждому исходному символу назначают отдельное кодовое слово одинаковой длины i. Одинаковый код для двух символов не позволит восстановить их различие. Для наших задач заранее известны начало сообщения и длина каждого слова; о секретности такая договорённость ничего не обещает.

Как составить полный перечень

Полный перечень строят по порядку, чтобы не считать один вариант дважды. Сначала фиксируют первый знак 0 и перебирают все разрешённые продолжения, затем повторяют тот же порядок с первым знаком 1. Внутри одного слова оба знака можно повторять, но каждое различное слово в перечень включают один раз. Начальный ноль полноценен: 001 и 101 — разные трёхпозиционные слова, а 001 и 1 имеют разную длину. В A1 составь перечни самостоятельно до раскрытия разбора. Картинка рядом иллюстрирует выбор, а точное число вариантов определяется условием.

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

Каждое уже составленное слово можно продолжить двумя способами: добавить 0 или добавить 1. Поэтому число слов при добавлении одной позиции удваивается. Для i позиций это произведение i двоек, которое записывают как 2^i. Степень здесь сокращает повторное умножение; складывать двойки нельзя. Вместимость означает число всех разных слов данной длины, а не число слов, которые мы обязаны использовать. Это можно проверить перечнем и правилом группировки, без перевода двоичных записей в десятичные числа.

Иллюстрация поясняет понятие. Точные данные и правила задаются текстом урока.

Достаточность и минимальность

Длина достаточна, если слов хватает всем N исходным символам: N ≤ 2^i. Чтобы доказать минимальность, покажи ещё и нехватку при предыдущей длине. Например, для нового набора из 18 символов 4 позиции дают 16 слов и не подходят, а 5 дают 32 и подходят. Минимальная длина 5. Нельзя остановиться на случайной большей длине, хотя она тоже вместит набор. Логарифмы не требуются: начинай с 2 и удваивай до первого подходящего значения.

Неназначенные коды допустимы

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

Собственная таблица и проверка партнёром

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

Как проверять уверенный ответ помощника

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

Условия и данные

Сначала попробуй сам

A1. Перечисли все двоичные слова длины 2, затем все слова длины 3. Внутри слова 0 и 1 могут повторяться, нули в начале разрешены. Каждое различное слово выпиши один раз. Как убедиться, что ничего не пропущено?

Подсказка при затруднении: Начни со всех слов с 0, затем со всех с 1. Для каждого начала перечисляй одинаковые продолжения.

K1. Исходный алфавит содержит 6 разных символов. Каждому нужен свой двоичный код одинаковой длины. Найди минимальную длину и число неназначенных кодов. Обоснуй, почему более короткая запись не подходит.

Подсказка при затруднении: Сравни число доступных комбинаций для соседних длин с числом исходных символов.

B1. Помощник выбрал для 5 значков длину 4, потому что 16 ≥ 5. Длина достаточна? Минимальна? Укажи минимальную и сколько кодов при ней останется свободными.

Подсказка при затруднении: Достаточность — всем хватило. Минимальность — более короткой длины уже не хватает.

R1 — новый случай. Новый исходный алфавит содержит 9 символов. Выбери минимальную длину и число свободных кодов. Не обязательно выписывать все коды; покажи два сравнения.

Подсказка: Проверь соседние длины, а не только одну подходящую.

Практика P1

А кодирует шесть символов {К, Л, М, Н, О, П}, Б — семь {Р, С, Т, У, Ф, Х, Ц}. Каждый выбери минимальную длину, составь свою полную таблицу разных кодов и назови неназначенные. А кодирует КМП, Б кодирует РТЦ. Передай партнёру свою таблицу и код: он восстанавливает сообщение по твоему правилу. Сохрани таблицу, код и объяснение в своём TXT.

1. 1 мин: прочитай полное условие P1; учитель уточняет режим и общую модель.
2. 2 мин: каждый отдельно составь решение/таблицу на бумаге. Начни именно со своих исходных данных.
3. 3 мин А: набери собственное решение, сохрани файл в выданную папку, закрой и снова открой. Б проверяет собственную бумажную запись.
4. 3 мин Б: выполни те же действия в отдельном файле; файл А не заменяй.
5. 1 мин: проверь результат партнёра по его данным и правилу; сверяй вывод и основание. Исправления вносит автор после своей попытки.

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

Проверяем ответ ИИ

Вымышленный совет: «Для 7 символов хватит 3 позиций, потому что 2 + 2 + 2 = 6. Код 001 можно сократить до 1». Найди ошибки в обосновании и записи; сформулируй проверяемую замену.

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

Новый случай и помощь

D1 — резерв после основного. Резерв: алфавит увеличился с 8 до 9 символов. На сколько увеличится минимальная длина? А при росте с 9 до 15? Объясни без логарифмов.

Подсказка: Запиши вместимости 4, 8, 16 и найди нужный промежуток.

Если трудно читать, учитель читает полное условие. Допустимы короткие фразы, увеличенная печать и устное объяснение с записью взрослым. Сначала личная попытка; партнёрская подпись не подтверждает личного действия за ПК. Опора: i позиций → сколько разных слов? N символов → хватит ли? Сначала полное перечисление, затем удвоение. Нули можно обвести; они не являются лишними.

Индивидуальный итог

Три минуты самостоятельно. Условия прочитай до начала; разбор открой после своей записи.

E1. Сколько разных двоичных слов длины 4?

E2. Для 10 символов выбери минимальную длину равномерного двоичного кода. Докажи минимальность.

E3. При выбранной в E2 длине сколько кодов останется неназначенными? Можно ли убрать ноль из начала одного кодового слова?

Разбор после попытки

Показать ответ после выполнения

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

Материалы и самостоятельная проверка

В карточках — презентация «Сигнал», самостоятельный план учителя, рабочий лист, отдельный выходной билет и бумажная самопроверка. Интерактив ниже содержит шесть вопросов, пояснение к выбранному варианту и новые примеры после попытки. Это отдельные 5–7 минут после основного занятия или при самостоятельной работе.

• Рабочий лист для печати

• Выходной билет: два на А4

• Шесть вопросов на бумаге

Домашний перенос

4–6 минут на бумаге. Для 12 значков найди минимальную одинаковую длину двоичных кодов, докажи двумя сравнениями и подсчитай свободные коды. Назначь любые три разных кода трём выбранным значкам. Сохраняй нули; компьютер не нужен.

Источники

Урок соотнесён с федеральной рабочей программой базового курса информатики 7–9 классов и рекомендациями на 2026/27. ИИ включён в предметные примеры с проверкой вымышленного совета. Команды редактора и правила кабинета учитель уточняет перед занятием.

• Федеральная рабочая программа информатики 7–9, базовый уровень, 2025, с. 7, 25–26

• Методические рекомендации по информатике на 2026/27, с. 3–5

• University of Canterbury: Data representation — binary digits and combinations

• NIST: двоичные приставки, байт и десятичные единицы