Четверичная система счисления

Четверичная система счисления (Quaternary Base Number System, QBNS) — это позиционная система с основанием 4. В отличие от привычной десятичной системы, где используется десять цифр (0–9), в четверичной системе применяются всего четыре цифры: 0, 1, 2 и 3.

По аналогии с «байтом» (byte, 8 бит) и «найблом» (nybble, полубайт, 4 бита) четверичную цифру иногда называют «крамом» (crumb, 2 бита).

Принцип позиционности означает, что значение каждой цифры зависит от её места (разряда) в записи числа, то есть каждый крам является коэффициентом при четвёрке (основании системы) в степени соответствующего разряда (позиции в числе, считая справа-налево, начиная с нуля). Например, число `123_4` в четверичной системе расшифровывается как:

`123_4 = 1*4^2+2*4^1+3*4^0 =` `1*16+2*4+3*1 = 27_10`

Если что, десятичная система тоже позиционная, и в ней всё то же самое:

`123_10 = 1*10^2+2*10^1+3*10^0 =` `1*100+2*10+3*1 = 123_10` :)

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

Для начала немного истории.

В Древней Бактрии была письменность «кхароштхи», заимствованная из арамейского письма ещё в I тысячелетии до н.э. и использовавшаяся местами почти до VII века н.э. В ней числительные представляли собой частичную четверичную систему счисления: были цифры 1, 2, 3, 4, а отдельных знаков для цифр 5–9 не было вообще (зато были 10, 20, 100 и 1000). Числа «набирались» как у римлян, но записывались справа налево и не было правила вычитания, только сложение.

К примеру, число 1996 записывалось вот так: 𐩇𐩃𐩃𐩀𐩆𐩅𐩅𐩅𐩅𐩄𐩃𐩁.

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

Речь о записях Фрая (отца) Хуана де ла Круса (Juan de la Cruz). Примерно в 1819 году, во время работы в католической миссии Сан-Буэнавентура (от которой и получил название диалект), он составил один из первых словарей языка вентуреño. В нём он привёл числительные вплоть до 32. Базовыми «кирпичиками» для счёта были 4, 8 и 16 (которое само является 4×4), остальные числа строились комбинаторно сложением и повторением (с применением чисел 1 и 2 как показателя):

• 1 — kampake’et («просто один»)
• 2 — ’iškom̓ (показатель двойки, часто используется как морфема в составе других числительных)
• 3 — yǝti’iškom̓ («ещё один к двум», то есть «2+1»)
• 4 = 4 — tskumu (отдельный корень для «четырёх»; именно он становится базовой единицей счёта)
• 5 = 4+1 — yǝtipake’es («ещё один» сверху к четырём по-умолчанию)
• 6 = 4+2 — tskumu ’iškom̓ («ещё два к четырём»)
• 7 = 4+3 — непонятно как звучало, скорее всего tskumu yǝti’iškom̓
• 8 = 8 — malawa (тоже отдельный корень, а не «4+4»)
• Числа от 9 до 12 строились как «8+N»
• Числа от 13 до 15 строились по-разному, как «8+N» или через четвёрки «4*3+N»
• 16 = 16 — tšikipš (следующий отдельный кирпичик)
• 17 = 16+1 — tšikipš kampake’et
• 20 = 4*5 — tskumu ’uy (возможно, связано с «пять четвёрок»)
• 24 = 16+4*2 — tšikipš tskumu-’iškom̓
• 25 = 16+4*2+1 — tšikipš tskumu-’iškom̓ kampake’et
• 26 = 16+4*2+2 — tšikipš tskumu-’iškom̓ ’iškom̓
• 28 = 16+4*3 — tšikipš tskumu-yǝti’iškom̓
• 31 = 16+4*3+3 — tšikipš tskumu-yǝti’iškom̓ yǝti’iškom̓
• 32 = 2*16 — ’iškom̓ tšikipš («две шестнашки»)

То есть в языке не было единой цепочки вроде «десять, двадцать, тридцать», как в десятичной системе. Вместо этого счёт шёл блоками по 4, иногда применялся кирпичик 8, а 16 выступало как более крупный «шаг». Похоже, что следующим крупным шагом могло быть 256 (16×16), но история об этом умалчивает.

На самом деле, мне это напоминает скорее не четверичную систему, а начало более логичной системы, построенной на степенях двойки: `2^0, 2^1, 2^2, 2^3, 2^4 = 1, 2, 4, 8, 16`. В любом случае, система (или дошедшее до нас её описание) хотя и была какая-то очень урезанная, но четвёрка в ней имела очень важное значение.

Эти примеры показывают, что основа 4 для счёта не является каким-то искусственным изобретением, а представляет собой естественный способ мышления и счёта, возникавший в разных культурах по всему миру независимо от десятичной системы, к которой мы привыкли.

Как и восьмеричная и шестнадцатеричная системы счисления, четверичная имеет особое отношение к двоичной системе счисления. Основания этих систем (4, 8 и 16) являются степенями двойки, поэтому преобразование в двоичную систему и обратно осуществляется путем сопоставления каждой цифры с двумя, тремя или четырьмя битами (двоичными цифрами 0 или 1). Например, в четверичной системе счисления каждую четверичную цифру можно представить двумя битами: 230210₄ = 10 11 00 10 01 00₂.

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

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

Четверичные таблицы сложения и умножения:

Поскольку 16 — это 4², преобразование между этими системами счисления можно осуществить путем сопоставления каждой шестнадцатеричной цифры с двумя четверичными. В приведенном выше примере: B24₁₆ = 23 02 10₄.

Давайте попробуем сравнить, что удобнее использовать в промежутке – десятеричную систему или четверичную.

Например, нужно сложить `1E6_16+B24_16=?` Вначале все шестнадцатеричные цифры переведём в десятичные числа, затем сложим их в столбик поразрядно справа налево. Перенос делаем, если результат >15.

То есть видим обычное сложение в столбик. Дополнительно перед глазами, если не помним, держим перекодировочную таблицу для ABCDEF. А теперь попробуем сделать всё то же самое, но используя в качестве промежуточной системы четверичную. Точно так же переводим в четверичные, считаем в столбик, переносим, если результат получился больше двух четверичных цифр, то есть >33.

В принципе, всё то же самое, количество шагов то же, вот только легче ли? Давайте посмотрим на 5-й шаг. Что легче воспринимается `1+1+11=13_10` или `1+1+23=31_4`? По мне так первое, потому что с детства нас учили десятичной системе, и считаем мы на автопилоте именно в ней. И то, что после 11 идёт 12 и 13 – это знает каждый ребёнок. А вот то, что в четверичной системе после 23 идёт 30 и 31 наш мозг на автопилоте не выдаёт, поэтому `1+1+23 = 31` вообще ни капли не очевидно. Приходится в момент расчёта «тормозить» и переключать мышление на четверичную систему, а это может вызвать определённые трудности.

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

Теперь попробуем посчитать «в столбик» умножение `1A_16 * 2B_16 = ?`. Вначале используем промежуточную десятичную систему.

• Шаг 1: умножаем `1A_16` на `B_16`
• `A*B=10*11=110_10`; `110:16=6` и остаток `14(E)` → `6E_16` → пишем `E`, переносим `6`
• `1*B=11`, плюс перенесённые `6` → `17_10 = 11_16`, пишем `11`
• Итого первая строка: `11E_16`

• Шаг 2: умножаем `1A_16` на `2_16` (со сдвигом)
• `A*2=10*2=20_10=14_16` → пишем `4`, переносим `1`
• `1*2=2`, плюс перенесённая `1` → `3_16`, пишем `3`
• Получили `34`, со сдвигом это `340_16`

• Шаг 3: складываем в столбик `11E_16` и `340_16`
• `E+0=E`, `1+4=5`, `1+3=4`, повезло – нет переносов
• Получаем `45E_16`

• Итого: `1A_16 * 2B_16 = 45E_16`.

А теперь всё то же самое, но проводим промежуточные вычисления в четверичной системе. Мне кажется, я сломаю мозг сейчас… Держим перед глазами «перекодировочную» таблицу и таблицы сложения и умножения:

• Шаг 1: Переводим числа в четверичные
• `1A_16 = 01` `22_4 = 122_4`; `2B_16 = 02` `23_4 = 223_4`

• Шаг 2: Умножаем `122_4` на `223_4` «в столбик» в четверичной арифметике

• Умножение на младшую цифру (3)
• Посчитаем `122_4*3_4`
• `2*3=6`. В четверичной: `6=1*4+2=12_4`, пишем `2`, переносим `1`.
• `2*3+1=6+1=7`. `7=1*4+3=13_4`, пишем `3`, переносим `1`.
• `1*3+1=3+1=4`. `4=10_4`, пишем `0`, переносим `1`; затем пишем `1`.
• Получаем первую строку: `1032_4`

• Умножение на среднюю цифру (2), со сдвигом на 1 разряд
• Считаем `122_4 * 2_4`, результат запишем со сдвигом
• `2*2=4=10_4`, пишем `0`, переносим `1`.
• `2*2+1=5=11_4`, пишем `1`, переносим `1`.
• `1*2+1=3`, пишем `3`.
• Получили `310_4`, со сдвигом это `3100_4`.

• Умножение на старшую цифру (2), со сдвигом на 2 разряда
• Считаем `122_4 * 2_4` ещё раз (это та же строка, что и выше) и сдвигаем на два разряда:
• Это будет `31000_4`.

• Шаг 3: Сложение строк в четверичной системе
• Складываем в столбик `1032_4`, `3100_4` и `31000_4`.
• Делаем по разрядам справа налево, помня, что при сумме ≥4 переносим 1 в следующий разряд (поскольку `4=10_4`).
• Разряды (справа налево, нумерация с 0):

1. Разряд 0: `2+0+0=2` → пишем `2`.
2. Разряд 1: `3+0+0=3` → пишем `3`.
3. Разряд 2: `0+1+0=1` → пишем `1`.
4. Разряд 3: `1+3+1=5`. `5=11_4`, пишем `1`, переносим `1`.
5. Разряд 4: `0+0+3+1`(перенос)`=4`. `4=10_4`, пишем `0`, переносим `1`.
6. Разряд 5: только перенос `1` → пишем `1`.

• Результат сложения: `1032_4 + 3100_4 + 31000_4 = 101132_4`

• Шаг 4: Переводим обратно в шестнадцатеричную
• `10` `11` `32_4 = 45E_16`

Ну и что, легче использовать четверичную по сравнению с десятеричной? Скажу так: да, можно конечно и складывать и умножать шестнадцатеричные числа через четверичную как промежуточную систему — это работает, потому что `16=4^2`. Но на практике это очень неудобно и ни капли не легче: легко можно лишь ошибиться в переносах, да и считать намного дольше, чем просто в шестнадцатеричной или через десятичную, а потому и тут больше места для ошибок. Поэтому для обычных расчётов (особенно на бумажке) люди четверичную систему не используют. И я не советую :)

Кстати, когда мы делаем сдвиг в десятичной системе (с приписыванием нолика), то получаем последовательность `10, 100, 1000, 10000`, потому что это `10^1, 10^2, 10^3, 10^4`. То есть сдвиг на n разрядов в десятичной системе эквивалентен умножению на `10^n`. А если мы сдвигаем в четверичной системе, то получаем последовательность `4^n`: `4, 16, 64, 256`. Но если записать эти числа в четверичной системе, то получим те же `10_4, 100_4, 1000_4, 10000_4`. Потому что, к примеру, `64_10 = ①*4^3+⓪*4^2+⓪*4^1+⓪*4^0 = 1000_4`. Красиво? Да. А ещё `4_10 = 10_4`! Вот для таких «штучек» четверичную систему и можно применять :)

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

В передаче данных используются четвертичные линейные коды, такие как 2B1Q (2 Binary, 1 Quaternary), применяемые в стандарте ISDN (цифровые телефонные сети) и в гигабитных Ethernet-сетях. Суть этого подхода в том, что сигнал может принимать не два состояния (0 и 1), а четыре. Это позволяет передавать два бита информации за один такт, фактически удваивая скорость передачи данных без увеличения частоты сигнала.

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

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

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

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

Четверичная система неожиданным образом связана с молекулярной биологией. ДНК состоит из четырёх типов нуклеотидов: Аденин (A), Цитозин (C), Гуанин (G) и Тимин (T). По сути, генетический код представляет собой естественную четверичную систему.

Эта аналогия позволяет:

• Кодировать последовательности ДНК в виде четверичных чисел. Например, последовательность GATTACA может быть представлена как `2033010_4` (что равно `9156_10`).
• Использовать методы обработки цифровых сигналов для анализа генетических данных.
• Рассматривать возможность создания биокомпьютеров, работающих на принципах четверичной логики, что может стать следующим шагом в развитии вычислительной техники.

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

Несмотря на удобство перевода в двоичную систему, четвертичная система не получила широкого распространения в вычислениях по нескольким причинам:

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

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

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

Вот несколько конкретных примеров.

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

• Квесты и «выход из комнаты»: В игре «Schizm 2. Хамелеон» есть головоломка, построенная на четверичной системе. По ходу игры игрок встречает три символа, с каждым из которых у него должно ассоциироваться определённое число (в игре это 16, 15 и 9). На очередной головоломке нарисованы эти три символа, а под каждым из них находится своеобразный кодовый трёхпозиционный замок (как на чемодане или в камере хранения). В каждой позиции можно выбрать 4 разных цифры. То есть задача сводится к тому, чтобы вместо `16_10`, `15_10` и `9_10` набрать на кодовом замке `100_4`, `033_4` и `021_4`. Это классический пример использования системы счисления как части игровой механики.

• Математические головоломки: Ziggu — это семейство головоломок, которые напрямую кодируют своё состояние в виде четверичного числа (числа с основанием 4). Каждая цифра этого числа соответствует положению элемента в одном из лабиринтов-головоломок. Интересно, что решение этих головоломок следует четверичному коду Грея — специальной последовательности чисел, где каждое следующее число отличается от предыдущего только в одном разряде. Это роднит их с классическими головоломками типа меледы, Ханойской башни и подобным им. При решении меледы и Ханойской башни применяют бинарные коды Грэя, в игре «Башня Бухареста» – тернарные (троичные), а в Ziggu – их более сложное, четверичное воплощение. Про двоичный код Грэя я уже упоминал, когда рассказывал про свою игру NBIN, и в Сказе о том, как я за ёлками ходил.

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

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

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

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

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

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

Есть целый пласт игр, которые формально используют некую «четверную» технологию, хотя никакого отношения именно к четверичной системе счисления это не имеет. Например, игры, которые рассчитаны на четверых игроков и имеющие соответственно 4 типа игровых элементов разного цвета 🔴🟢🟡🔵:

• Шахматы для четверых

• Невские шашки

• Классическое «Ludo»

Есть игры, рассчитанные на любое число игроков, но тем не менее с четырьмя типами игровых элементов, например карточные игры с классическими четырьмя мастями ♠️♥️♣️♦️:

Однажды, разглядывая логотип известной операционной системы, мне пришла в голову мысль сделать на базе этого шифр. Получился настоящий "четверичный" шифр, в котором каждому краму соответствует своё уникальное графическое представление 🟥🟦🟨🟩, четверичные числа получаются в виде цветных квадратиков, как мозаика, а зашифрованный текст выглядит вот так:

Попробуйте расшифровать, используя эти кодировочные таблицы:

Четверичная система счисления — это не просто абстрактная концепция из курса информатики, но мощный и гибкий инструмент, который:

• ⛰️ Возникал естественным путём у разных народов,
• 📡 Эффективно используется в телекоммуникациях для повышения скорости передачи данных,
• 🧮 Вносит вклад в развитие энергоэффективной и высокоточной электроники,
• 🔬 Находит неожиданное применение в моделировании генетического кода,
• 🎨 Помогает решать задачи в области компьютерной графики,
• 🧩 Может стать основой для создания занимательных головоломок, игр и квестов.

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

• https://arxiv.org/pdf/2411.19291 – The quaternary Gray code and how it can be used to solve ZigguRat and other Ziggu puzzles