12 мин чтениясистемы счислениякодированиеобъём информацииусловие ФаноКЕГЭ
Системы счисления и кодирование информации
Перевод между системами счисления, арифметика в разных основаниях, объём информации, равномерные и префиксные коды.
Открываем тему…
Позиционные системы счисления
В позиционной системе с основанием p значение цифры зависит от её позиции. Число aₙ…a₁a₀ в системе с основанием p равно сумме aᵢ·pⁱ. На экзамене чаще всего встречаются системы 2, 8, 16, а также нестандартные основания (3, 5, 7, 9, 12), в которых нужно выполнять сложение, сравнение и поиск неизвестных цифр.
- Из десятичной в p-ичную: делим на p с остатком, остатки читаем снизу вверх.
- Из двоичной в восьмеричную — группы по 3 бита, в шестнадцатеричную — группы по 4 бита.
- Количество цифр числа N в системе p: ⌊log_p N⌋ + 1.
- Последняя цифра числа в системе p — остаток от деления на p; число делится на p ⇔ оно оканчивается нулём.
ПримерНеизвестная цифра
Значение выражения 7⁸ + 7⁵ − 49 записали в семеричной системе. Сколько цифр 6 в этой записи?
Решение
Представим 7⁸ + 7⁵ − 7². Разность 7⁵ − 7² = 7²(7³ − 1) = 7²·(343 − 1) = 7²·342; 342 = 666₇ (6·49+6·7+6). Тогда 7²·666₇ = 66600₇. Складываем с 7⁸ = 100000000₇: получаем 100066600₇. Шестёрок — 3.
Кодирование и объём информации
- 1 байт = 8 бит; 1 Кбайт = 2¹⁰ байт; 1 Мбайт = 2²⁰ байт.
- Растровое изображение: I = W·H·i, где i — глубина цвета в битах.
- Звук: I = f·i·t·k (частота дискретизации, разрядность, длительность, число каналов).
- Неравномерный код: если слова разной длины, нужно выполнить условие Фано (ни одно кодовое слово не является началом другого) для однозначной декодировки.
ПримерМинимальная длина кода
Для передачи используется равномерный двоичный код символов алфавита из 70 символов. Сколько байт займёт сообщение из 400 символов?
Решение
2⁶ = 64 < 70 ≤ 128 = 2⁷, значит i = 7 бит. 400·7 = 2800 бит = 350 байт.
ПримерСравнение чисел в разных системах
Какое из чисел наибольшее: 101101₂, 57₈, 2C₁₆ или 46₁₀?
Решение
Переводим всё в десятичную систему: 101101₂ = 32 + 8 + 4 + 1 = 45; 57₈ = 5·8 + 7 = 47; 2C₁₆ = 2·16 + 12 = 44; 46₁₀ = 46. Наибольшее — 57₈ (47).
Проверка на Python:
print(int('101101', 2), int('57', 8), int('2C', 16), 46)
ПримерОснование системы из равенства
В некоторой системе счисления с основанием p верно равенство 13 + 24 = 40. Найдите p.
Решение
Раскладываем записи по степеням основания: 13 = p + 3, 24 = 2p + 4, 40 = 4p. Равенство: (p + 3) + (2p + 4) = 4p ⇒ 3p + 7 = 4p ⇒ p = 7. Проверка: все цифры (1, 2, 3, 4, 0) меньше 7; 13₇ = 10, 24₇ = 18, 40₇ = 28, и 10 + 18 = 28.
Проверка перебором:
for p in range(5, 37):
if (p + 3) + (2 * p + 4) == 4 * p:
print(p)
ПримерВремя передачи файла
Файл объёмом 15 Мбайт передаётся по каналу со скоростью 4 194 304 бит/с. Сколько секунд длится передача?
Решение
Переводим в биты: 15 Мбайт = 15·2²⁰ байт = 15·2²³ бит. Скорость 4 194 304 = 2²² бит/с. Время t = I / v = 15·2²³ / 2²² = 15·2 = 30 с.
В КЕГЭ почти всегда удобно записывать все величины степенями двойки и сокращать их, а не перемножать большие числа.
ПримерЧисла без нуля в записи
Сколько существует трёхзначных чисел в пятеричной системе счисления, в записи которых нет цифры 0?
Решение
Каждая из трёх позиций (включая старшую) принимает значения 1, 2, 3 или 4 — по 4 варианта: 4·4·4 = 64.
Проверка на Python (трёхзначные пятеричные числа — это десятичные 25…124):
def to5(n):
s = ''
while n:
s = str(n % 5) + s
n //= 5
return s
print(sum(1 for n in range(25, 125) if '0' not in to5(n)))
Интерактивная иллюстрация