Кодирование и обработка чисел в вычислительных системах

Системы счисления и преобразование чисел

Зачем нужны системы счисления в вычислительных системах

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

В этой статье разберём:

что такое система счисления и основание
как читается позиционная запись числа
как переводить целые и дробные числа между основаниями
как быстро переводить между 2, 8 и 16

Основные понятия

Система счисления — способ записи чисел с помощью набора символов (цифр) и правил.

Основание системы счисления (часто обозначают $b$ ) — количество различных цифр, которые используются в системе.

В десятичной системе $b = 10$ , цифры: 0–9
В двоичной системе $b = 2$ , цифры: 0–1
В восьмеричной системе $b = 8$ , цифры: 0–7
В шестнадцатеричной системе $b = 16$ , цифры: 0–9 и A–F (где A=10, B=11, ..., F=15)

Позиционные и непозиционные системы

Позиционная система счисления — система, где значение цифры зависит от её позиции (разряда) в записи числа.

Пример: в числе 505 цифра 5 слева означает пять сотен, а 5 справа — пять единиц.

Непозиционные системы встречаются реже (пример — римские числа), и в вычислительных системах почти не используются из-за неудобства арифметики.

Как позиционная запись превращается в значение числа

Целая часть

Если число записано в системе с основанием $b$ как последовательность цифр $a_n a_{n-1} ... a_1 a_0$ , то его значение равно сумме разрядов:

N = \sum_{i=0}^{n} a_i \cdot b^i

Разберём элементы формулы:

$N$ — значение числа (в привычном смысле)
$\sum$ — знак суммирования: нужно сложить вклад каждого разряда
$i$ — номер разряда, начиная с 0 справа (разряд единиц)
$a_i$ — цифра в разряде $i$ (она всегда меньше основания: $0 \le a_i < b$ )
$b$ — основание системы счисления
$b^i$ — вес разряда (например, для десятичной: $10^0=1$ , $10^1=10$ , $10^2=100$ )

Пример: переведём $1011_2$ в десятичное значение.

справа налево разряды: $1\cdot 2^0$ , $1\cdot 2^1$ , $0\cdot 2^2$ , $1\cdot 2^3$
получаем: $1\cdot 1 + 1\cdot 2 + 0\cdot 4 + 1\cdot 8 = 11$

Значит, $1011_2 = 11_{10}$ .

Дробная часть

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

Если запись выглядит как $a_0.a_{-1}a_{-2}...$ (точка — разделитель), то вклад дробной части:

F = \sum_{k=1}^{m} a_{-k} \cdot b^{-k}

$a_{-1}$ — первая цифра после точки
$b^{-1} = \frac{1}{b}$ , $b^{-2} = \frac{1}{b^2}$ и так далее

Пример: $0.11_2$ .

$1\cdot 2^{-1} + 1\cdot 2^{-2} = \frac{1}{2} + \frac{1}{4} = 0.75$

Значит, $0.11_2 = 0.75_{10}$ .

Часто используемые основания и их цифры

Основание	Название	Допустимые цифры	Где встречается
2	двоичная	0–1	внутренняя логика и память компьютера
8	восьмеричная	0–7	компактная запись двоичных данных (исторически)
10	десятичная	0–9	повседневная запись чисел
16	шестнадцатеричная	0–9, A–F	адреса памяти, машинные коды, цвета, хеши

Перевод чисел в десятичную систему

Из любой системы в десятичную (целые)

Алгоритм:

пронумеровать разряды справа налево, начиная с 0
умножить каждую цифру на соответствующий вес $b^i$
сложить результаты

Пример: $2A_{16}$ .

$A_{16} = 10_{10}$
$2A_{16} = 2\cdot 16^1 + 10\cdot 16^0 = 32 + 10 = 42$

Значит, $2A_{16} = 42_{10}$ .

Из любой системы в десятичную (дробные)

Алгоритм:

для цифр после точки использовать веса $b^{-1}, b^{-2}, ...$
суммировать вклад

Пример: $0.625_{10}$ в двоичной системе мы пока не переводим, но для обратного направления полезно понимать: если бы было $0.101_2$ , то это $1\cdot 2^{-1} + 0\cdot 2^{-2} + 1\cdot 2^{-3} = 0.625$ .

Перевод из десятичной системы в другую (целые числа)

Самый практичный способ для целых чисел — деление с остатком.

Алгоритм перевода $N_{10}$ в основание $b$ :

Разделить $N$ на $b$ , запомнить остаток.
Результат деления снова разделить на $b$ , опять запомнить остаток.
Повторять, пока частное не станет равно 0.
Ответ — остатки, прочитанные в обратном порядке.

Пример: переведём $45_{10}$ в двоичную.

Деление	Частное	Остаток (бит)
$45 \div 2$	22	1
$22 \div 2$	11	0
$11 \div 2$	5	1
$5 \div 2$	2	1
$2 \div 2$	1	0
$1 \div 2$	0	1

Читаем остатки снизу вверх: $101101_2$ .

Значит, $45_{10} = 101101_2$ .

Перевод из десятичной системы в другую (дробные числа)

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

Идея: при умножении дроби на $b$ целая часть результата становится очередной цифрой после точки.

Алгоритм для дроби $0.f$ в основание $b$ :

Умножить дробную часть на $b$ .
Целая часть произведения — следующая цифра.
Новая дробная часть — дробная часть произведения.
Повторять до получения 0 или до нужной точности.

Пример: переведём $0.625_{10}$ в двоичную.

Шаг	Умножаем на 2	Целая часть (бит)	Новая дробная часть
1	$0.625\cdot 2 = 1.25$	1	0.25
2	$0.25\cdot 2 = 0.5$	0	0.5
3	$0.5\cdot 2 = 1.0$	1	0.0

Получили $0.101_2$ .

Важно: не всякая десятичная дробь имеет конечную запись в двоичной системе. Например, $0.1_{10}$ в двоичной системе будет бесконечной периодической дробью. В вычислительных системах это приводит к погрешностям представления, к которым мы вернёмся в следующих темах.

Быстрые переводы между 2, 8 и 16

Поскольку:

$8 = 2^3$
$16 = 2^4$

можно переводить без деления и умножения — группируя биты.

Двоичная ↔ восьмеричная

чтобы получить восьмеричную запись из двоичной: разбить двоичное число справа налево на группы по 3 бита
каждая тройка бит — одна восьмеричная цифра

Пример: $110101011_2$ .

группируем: $110\ 101\ 011$
переводим тройки: $110_2=6$ , $101_2=5$ , $011_2=3$

Получаем $653_8$ .

Двоичная ↔ шестнадцатеричная

разбить справа налево на группы по 4 бита
каждая четвёрка — одна шестнадцатеричная цифра

Пример: $111100001011_2$ .

группируем: $1111\ 0000\ 1011$
переводим: $1111_2=F$ , $0000_2=0$ , $1011_2=B$

Получаем $F0B_{16}$ .

Шестнадцатеричная ↔ восьмеричная

Прямого группирования нет (4 и 3 не совпадают). Практически делают так:

перевести 16 → 2 (каждый hex-символ в 4 бита)
затем 2 → 8 (группы по 3 бита)

Практические соглашения записи

Чтобы не путать основания, используют обозначения:

индекс: $1011_2$ , $77_8$ , $255_{10}$ , $FF_{16}$
или префиксы (в языках программирования): 0b1011, 0o77, 255, 0xFF

Важно: префиксы зависят от языка и его правил, а индекс $\_b$ — универсальная учебная запись.

Типичные ошибки при переводе

Путать порядок чтения остатков в методе деления (остатки читаются снизу вверх).
Использовать недопустимые цифры для основания (например, цифру 8 в восьмеричной системе).
Забывать, что дроби могут получаться бесконечными (нужна остановка по точности).
Неверно группировать биты (группировать нужно от точки: для целой части — справа налево, для дробной — слева направо).

Что дальше по курсу

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

Источники для углубления

Двоичное кодирование целых: знаковые форматы и переполнение

Связь с предыдущей темой

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

Ключевая идея этой темы:

один и тот же двоичный шаблон (например, 11111111) может означать 255, -1 или другое число — это зависит от выбранного формата кодирования целых
из-за конечного числа битов существует ограниченный диапазон представимых значений, а выход за него приводит к переполнению

Битовая ширина и диапазон значений

Пусть у нас есть фиксированное количество битов $n$ (например, $n=8$ , $n=16$ , $n=32$ ). Тогда всего различных двоичных шаблонов:

2^n

Пояснение элементов формулы:

$n$ — количество битов в коде числа
$2$ — потому что каждый бит может быть либо 0, либо 1
$2^n$ — количество разных комбинаций (и, следовательно, потенциальных значений)

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

Беззнаковые целые

Беззнаковое (unsigned) кодирование трактует все биты как вклад в величину (нет отдельного признака “минус”).

Для $n$ бит диапазон:

0 \le N \le 2^n - 1

Пояснение:

$N$ — числовое значение
$2^n - 1$ — максимальное значение, когда все $n$ битов равны 1

Пример для 8 бит:

00000000 $= 0$
11111111 $= 255$

Беззнаковые числа удобны для:

размеров, счётчиков, индексов (там, где отрицательные значения не имеют смысла)
низкоуровневых битовых масок

Почему знаковые числа — отдельная тема

Хотим хранить и положительные, и отрицательные целые в фиксированных $n$ битах. Нужно ответить на два вопроса:

как кодировать знак
как выполнять арифметику (сложение/вычитание) так, чтобы аппаратно это было просто и быстро

Исторически существовало несколько подходов. Мы рассмотрим основные: прямой код, обратный код, дополнительный код. На практике сегодня доминирует дополнительный код.

Прямой код (sign-magnitude)

Идея: старший бит — это знак, остальные биты — модуль.

знак: 0 — плюс, 1 — минус
модуль: обычное беззнаковое число

Пример (8 бит):

00000101 = $+5$
10000101 = $-5$

Проблемы прямого кода:

два нуля: 00000000 = $+0$ , но также 10000000 = $-0$
сложение и вычитание сложнее: нужно отдельно учитывать знаки и модули

Из-за этого прямой код почти не используется для целочисленной арифметики общего назначения.

Обратный код (one’s complement)

Идея: положительные числа — как обычно, отрицательные получаются побитовым инвертированием положительного.

Как получить $-x$ из $x$ :

записать $x$ в двоичном виде
заменить каждый бит: 0 → 1, 1 → 0

Пример (8 бит):

$+5$ = 00000101
$-5$ = 11111010

Проблемы обратного кода:

снова два нуля: 00000000 и 11111111 (это $-0$ )
сложение требует “переноса через край” (end-around carry), что усложняет реализацию

Обратный код встречался в некоторых старых системах, но сейчас редок.

Дополнительный код (two’s complement) — стандарт де-факто

Дополнительный код (two’s complement) сегодня используется почти во всех массовых архитектурах и языках на уровне машинной арифметики.

Как получить отрицательное число $-x$ в $n$ битах:

записать $x$ в двоичном виде (в $n$ битах)
инвертировать все биты
прибавить 1

Пример (8 бит) для $-5$ :

$+5$ = 00000101
инверсия: 11111010
плюс 1: 11111011 значит $-5$

Почему это удобно

один ноль: 00000000
сложение и вычитание работают тем же сумматором, что и для беззнаковых чисел (в пределах $n$ бит)
знак “встроен” в арифметику: старший бит (MSB) часто интерпретируется как признак отрицательности

Диапазон значений в дополнительном коде

Для $n$ бит диапазон:

-2^{n-1} \le N \le 2^{n-1} - 1

Пояснение:

$n$ — количество битов
$N$ — интерпретируемое знаковое значение
$2^{n-1}$ связано с тем, что один бит (старший) играет роль знака и одновременно участвует в весах разрядов
минимальное значение $-2^{n-1}$ существует, а симметричного “ $+2^{n-1}$ ” нет, поэтому положительный максимум на 1 меньше

Пример для 8 бит:

минимум: $-128$ , код 10000000
максимум: $+127$ , код 01111111

Как один и тот же шаблон битов может означать разные числа

Рассмотрим 11111111 (8 бит):

как беззнаковое: это $255$
как дополнительный код: это $-1$

Вывод: биты сами по себе — это только код. Смысл появляется, когда мы выбираем интерпретацию (unsigned или signed).

Расширение знака (sign extension)

Частая операция: увеличить разрядность, например, из 8 бит сделать 16 бит, сохранив значение.

для беззнаковых: слева дописываем нули
для знаковых в дополнительном коде: слева дописываем копии старшего бита (бит знака)

Пример (8 → 16 бит):

$+5$ : 00000101 → 00000000 00000101
$-5$ : 11111011 → 11111111 11111011

Почему для отрицательных дописываются единицы: в additional code все старшие биты отрицательного числа равны 1, и такое расширение сохраняет значение.

Переполнение: что это и почему возникает

Переполнение — ситуация, когда результат операции не помещается в диапазон выбранного формата и разрядности.

Важно различать:

переполнение для беззнаковых (unsigned overflow)
переполнение для знаковых (signed overflow)

Потому что критерии “не помещается” разные.

Переполнение в беззнаковой арифметике

Если результат больше $2^n-1$ , то в аппаратной арифметике часто остаются только младшие $n$ бит (происходит “оборачивание” по модулю $2^n$ ).

Пример для 8 бит:

$255 + 1 = 256$ , но в 8 битах остаётся 00000000 (то есть 0)

Это поведение соответствует вычислениям по модулю:

N \bmod 2^n

Пояснение:

$N$ — “математический” результат без ограничения разрядности
$2^n$ — модуль, равный количеству возможных кодов
$\bmod$ — операция взятия остатка

Во многих языках и системах такое поведение для unsigned определено как стандартное.

Переполнение в знаковой арифметике (two’s complement)

В дополнительном коде переполнение происходит, когда истинный результат выходит за диапазон $[-2^{n-1},\;2^{n-1}-1]$ .

Практическое правило для сложения two’s complement:

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

Пример (8 бит):

$127$ = 01111111
$+1$ = 00000001
сумма (в 8 битах) = 10000000 (это $-128$ )

Математически $127 + 1 = 128$ , но 128 не представимо в 8-битном signed, поэтому возникает переполнение.

Переполнение и языки программирования: важная оговорка

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

для беззнаковых типов часто определено модульное поведение
для знаковых типов некоторые языки трактуют переполнение как ошибку, некоторые — как неопределённое или зависимое от платформы поведение

Для курса важно понимать базовый факт: аппаратно вы всегда ограничены $n$ битами и диапазоном представления.

Сводная таблица форматов (кратко)

Формат	Идея	Ноль	Удобство арифметики	Где встречается
Беззнаковый	все биты — величина	один	очень высокое	повсеместно
Прямой код	старший бит — знак, остальные — модуль	два нуля	низкое	редко, исторически
Обратный код	отрицательное = побитовая инверсия	два нуля	среднее/сложнее	редко, исторически
Дополнительный код	отрицательное = инверсия + 1	один	высокое	стандарт де-факто

Что важно запомнить

двоичный шаблон сам по себе не “знаковый” и не “беззнаковый” — это задаёт интерпретация
дополнительный код удобен тем, что даёт один ноль и простую аппаратную арифметику
при фиксированных $n$ битах всегда есть границы диапазона, а выход за них приводит к переполнению
для знакового two’s complement переполнение при сложении связано с “неожиданной сменой знака” результата при одинаковых знаках слагаемых

Источники для углубления

Фиксированная точка: масштабирование и точность

Как эта тема связана с предыдущими

В прошлых статьях мы разобрали:

как числа переводятся между системами счисления
как целые числа кодируются в двоичном виде (включая дополнительный код) и почему возникает переполнение

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

Фиксированная точка (fixed-point) — это способ кодирования дробных чисел, где двоичная точка считается стоящей в фиксированном месте, а все значения интерпретируются через заранее выбранный масштаб.

Что такое фиксированная точка

Идея простая: в памяти хранится целое число $I$ , но мы договорились, что настоящее значение $x$ получается умножением на масштаб.

Чаще всего в вычислительных системах масштаб выбирают степенью двойки.

Масштаб через степень двойки

Если мы выделяем $f$ битов под дробную часть, то масштаб равен $2^{-f}$ , и интерпретация такая:

x = I \cdot 2^{-f}

Пояснение элементов формулы:

$x$ — значение, которое мы хотим получить как вещественное число
$I$ — хранимое целое значение (в битах, обычно в two’s complement для знаковых)
$f$ — число дробных битов (сколько разрядов справа от двоичной точки)
$2^{-f}$ — масштаб, который «делит» целое на $2^f$

Эквивалентная запись (иногда понятнее):

x = \frac{I}{2^f}

знаменатель $2^f$ — это число уровней внутри единицы, которое задаёт дискретность

Как выглядит двоичная точка внутри битов

Если у нас есть, например, 8-битное значение и мы решили, что $f=3$ , то двоичная точка мысленно стоит перед тремя младшими битами.

Пример интерпретации

Пусть 8 бит, $f=3$ , а в памяти лежит:

00101010

Это как целое без знака равно $42$ . Тогда фиксированная точка даёт:

$x = 42 / 2^3 = 42 / 8 = 5.25$

То есть 00101010 в таком формате означает 5.25.

Формат Q и соглашения о записи

Часто фиксированную точку описывают через Q-формат.

Идея: указать, сколько битов относится к целой части и сколько к дробной.

Варианты записи встречаются разные, но распространённое практическое соглашение:

Qm.f — где $f$ это число дробных битов, а $m$ примерно соответствует числу битов целой части (включая знак или без — зависит от контекста)

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

вы выбираете ширину слова $n$
вы выбираете дробные биты $f$
значение всегда интерпретируется как $I / 2^f$

Диапазон значений и шаг (точность)

Шаг квантования

Если дробных битов $f$ , то минимальный «шаг» между соседними представимыми значениями:

\Delta = 2^{-f}

Пояснение:

$\Delta$ — шаг квантования (разрешение)
$f$ — число дробных битов
$2^{-f}$ — насколько меняется значение при увеличении $I$ на 1

Пример:

если $f=3$ , то $\Delta = 2^{-3} = 1/8 = 0.125$
значит, число не может иметь точность лучше 0.125: любая величина будет округлена к ближайшему кратному 0.125

Диапазон для знакового two’s complement

Если $I$ хранится в дополнительном коде и всего битов $n$ , то целочисленный диапазон $I$ :

от $-2^{n-1}$ до $2^{n-1}-1$

При фиксированной точке мы просто масштабируем этот диапазон делением на $2^f$ :

x_{\min} = -2^{n-1} \cdot 2^{-f}

x_{\max} = (2^{n-1}-1) \cdot 2^{-f}

Пояснение элементов:

$n$ — ширина слова в битах
$f$ — дробные биты
$2^{n-1}$ — модуль минимального целого в two’s complement
« $-1$ » в максимуме появляется из-за асимметрии диапазона two’s complement: отрицательных значений на одно больше
умножение на $2^{-f}$ переводит целый диапазон в дробный (деление на $2^f$ )

Пример: $n=8$ , $f=3$ .

$I_{\min}=-128$ , $I_{\max}=127$
$x_{\min}=-128/8=-16$
$x_{\max}=127/8=15.875$
шаг $\Delta=1/8=0.125$

Как кодировать число в фиксированной точке

На практике обычно делают так:

Выбирают $f$ (сколько дробных битов нужно для нужной точности).
Число $x$ умножают на $2^f$ .
Полученный результат округляют до целого и кладут в тип ширины $n$ .

То есть код $I$ получают как:

I = \operatorname{round}(x \cdot 2^f)

Пояснение:

$x$ — исходное число
$2^f$ — переносит «дробность» в целую область
$\operatorname{round}(\cdot)$ — выбранное правило округления (важно зафиксировать его)

Округление и ошибка представления

Поскольку фиксированная точка имеет шаг $\Delta$ , неизбежна ошибка квантования. Для округления к ближайшему ошибка обычно ограничена половиной шага:

|\varepsilon| \le \frac{\Delta}{2}

Пояснение:

$\varepsilon$ — ошибка между истинным $x$ и представимым значением
$\Delta$ — шаг квантования
деление на 2 — потому что округляем к ближайшему уровню

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

Арифметика фиксированной точки

Ключевой принцип: вы выполняете операции над целыми кодами $I$ , но обязаны следить за масштабом.

Сложение и вычитание

Если два числа имеют одинаковый $f$ (одинаковый масштаб), то:

складывать и вычитать можно прямо как целые
масштаб результата остаётся тем же

Пример (оба с $f=3$ ):

$x_1 = I_1/8$ , $x_2 = I_2/8$
$x_1 + x_2 = (I_1 + I_2)/8$

Главный риск — переполнение: ровно то же, что в целых, потому что внутри вы складываете $I_1 + I_2$ в ограниченной ширине $n$ .

Умножение

Если:

$x_1 = I_1/2^{f_1}$
$x_2 = I_2/2^{f_2}$

то произведение:

x_1 x_2 = \frac{I_1 I_2}{2^{f_1+f_2}}

Пояснение:

числитель $I_1 I_2$ — обычное целочисленное произведение кодов
дробные биты складываются: $f_1+f_2$

Практический вывод:

после умножения масштаб «становится мельче» (дробных битов больше)
чтобы вернуться к исходному формату (например, снова к $f$ ), обычно делают сдвиг вправо на нужное число битов

Если оба числа в одном формате с $f$ дробными битами, то типичный путь:

посчитать tmp = I1 * I2 в более широкой разрядности (например, 32-битное произведение из двух 16-битных)
сделать I = round(tmp / 2^f) то есть сдвиг вправо на $f$ (с округлением)

Главные риски:

промежуточное переполнение при умножении, если нет расширения разрядности
потеря точности при сдвиге вправо

Деление

Деление требует аккуратного сохранения масштаба. Если вы хотите получить результат в формате с $f$ дробными битами, часто делают так:

перед делением «поднимают» числитель: $I_1 \cdot 2^f$
затем делят на $I_2$

Идея: вы заранее добавляете место под дробную часть результата.

Главные риски:

деление на ноль
переполнение при предварительном умножении числителя на $2^f$

Переполнение и стратегии обработки

Из статьи про целые числа важно помнить: арифметика в фиксированной точке внутри остаётся целочисленной, поэтому переполнение возникает так же неизбежно.

Есть несколько распространённых стратегий:

оборачивание (wrap-around): остаются младшие $n$ бит (типично для unsigned и часто на уровне железа)
насыщение (saturation): при выходе за пределы результат «прилипает» к максимуму или минимуму
расширение разрядности: считать во временно более широком типе, а затем приводить

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

Выбор масштаба: компромисс между диапазоном и точностью

Выбор $f$ — это всегда обмен:

больше $f$ $f$
- лучше точность (меньше шаг $\Delta$ )
- меньше диапазон по модулю, потому что значимые биты уходят в дробную часть
меньше $f$ $f$
- больше диапазон
- хуже точность

Пример для $n=16$ (знаковый two’s complement):

Дробные биты $f$	Шаг $\Delta$	Примерный диапазон
0	1	от $-32768$ до $32767$
8	$1/256 \approx 0.00390625$	от $-128$ до $127.99609375$
12	$1/4096 \approx 0.000244140625$	от $-8$ до $7.999755859375$

Типичные ошибки при работе с фиксированной точкой

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

Где фиксированная точка используется на практике

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

Что дальше

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

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

Источники для углубления

Плавающая точка IEEE 754: структура, NaN, бесконечности

Связь с предыдущими темами курса

Ранее мы разобрали:

как числа переводятся между системами счисления;
как целые кодируются в двоичном виде (включая дополнительный код) и что такое переполнение;
как представлять дроби через фиксированную точку и почему там приходится вручную управлять масштабом $2^{-f}$ .

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

Стандартом де-факто для представления чисел с плавающей точкой в современных вычислительных системах является IEEE 754.

Интуиция: число как мантисса и степень

Идея плавающей точки похожа на научную запись:

$1.234 \cdot 10^3$ в десятичной форме;
в двоичной арифметике удобно хранить как $m \cdot 2^e$ .

Здесь:

$m$ — значащая часть (часто говорят мантисса или significand);
$e$ — показатель степени (экспонента).

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

Форматы IEEE 754: float32 и float64

На практике чаще всего встречаются два бинарных формата:

Формат	Бит всего	Бит знака $s$	Бит экспоненты $E$	Бит дроби $F$	В языках
binary32	32	1	8	23	`float` (часто)
binary64	64	1	11	52	`double` (часто)

Биты в IEEE 754 интерпретируются не как «целое со знаком», а как структура полей.

Что именно хранится в полях

Бит знака

Поле знака $s$ :

$s=0$ означает «плюс»;
$s=1$ означает «минус».

Экспонента и смещение (bias)

Экспонента хранится не как знаковое целое, а как смещённая величина.

Определим:

$E$ — значение поля экспоненты, прочитанное как беззнаковое число;
$\text{bias}$ — смещение (константа, зависящая от формата);
$e$ — «настоящая» экспонента, которая участвует в $2^e$ .

Связь задаётся формулой:

e = E - \text{bias}

Пояснение элементов формулы:

$e$ — экспонента, с которой число реально масштабируется;
$E$ — то, что физически записано в битах экспоненты;
$\text{bias}$ — смещение, чтобы в поле $E$ можно было хранить и отрицательные, и положительные $e$ без отдельного знака.

Для популярных форматов:

для binary32: $\text{bias}=127$ ;
для binary64: $\text{bias}=1023$ .

Дробь (fraction) и «скрытая единица»

Поле дроби $F$ содержит биты после двоичной точки. Для большинства обычных чисел (так называемых нормализованных) IEEE 754 использует приём скрытой ведущей единицы:

значащая часть начинается с $1.$ , но эту ведущую 1 не хранят, потому что в нормализованной форме она всегда одинакова.

Это экономит 1 бит точности.

Нормализованные числа: основной случай

Если поле экспоненты не все нули и не все единицы, число считается нормализованным.

Значение вычисляется так:

x = (-1)^s \cdot (1 + f) \cdot 2^e

Пояснение элементов:

$x$ — итоговое значение;
$(-1)^s$ — даёт знак (при $s=0$ это $+1$ , при $s=1$ это $-1$ );
$(1+f)$ — значащая часть: ведущая единица подразумевается, а $f$ — дробная добавка из поля $F$ ;
$2^e$ — масштабирование степенью двойки, где $e=E-\text{bias}$ .

Что такое $f$ :

если дробь состоит из битов $b_1 b_2 \ldots b_p$ (где $p$ — число битов дроби: 23 для float32, 52 для float64), то

f = \sum_{i=1}^{p} b_i \cdot 2^{-i}

Пояснение:

$b_i \in \{0,1\}$ — i-й бит дроби;
$2^{-i}$ — вес этого бита (первый бит после точки весит $1/2$ , следующий $1/4$ и т.д.).

Пример: почему 1.0 кодируется «красиво»

Для binary32 число $1.0$ имеет:

$s=0$ ;
$e=0$ ;
$f=0$ .

Тогда $x=(+1)\cdot(1+0)\cdot2^0=1$ .

Чтобы получить $e=0$ при bias 127, нужно $E=127$ , то есть двоично 01111111.

Нули и денормализованные (subnormal) числа

Если поле экспоненты все нули ( $E=0$ ), то стандарт разделяет два случая:

если дробь $F=0$ , то это ноль (причём бывает $+0$ и $-0$ );
если дробь $F \ne 0$ , то это денормализованное (subnormal) число.

Зачем нужны subnormal

Без subnormal был бы «разрыв» между:

самым маленьким положительным нормализованным числом;
нулём.

Subnormal заполняют этот промежуток и позволяют плавно “подходить к нулю”, ценой снижения точности.

Значение subnormal

Для subnormal ведущей единицы нет. Формула становится:

x = (-1)^s \cdot f \cdot 2^{1-\text{bias}}

Пояснение элементов:

$(-1)^s$ — знак;
$f$ — дробь, собранная из поля $F$ (как сумма $b_i\cdot2^{-i}$ );
$2^{1-\text{bias}}$ — фиксированная степень для всех subnormal данного формата; единица в показателе появляется из правил IEEE 754, чтобы обеспечить непрерывность с нормализованными значениями.

Особые значения: бесконечности и NaN

IEEE 754 резервирует комбинации, где поле экспоненты все единицы.

Для float32 это $E=255$ (в двоичном виде 11111111), для float64 это $E=2047$ .

Бесконечности

Если экспонента вся из единиц, а дробь нулевая ( $F=0$ ), то это бесконечность:

$s=0$ даёт $+\infty$ ;
$s=1$ даёт $-\infty$ .

Откуда они берутся в вычислениях:

деление ненулевого числа на 0 (в IEEE 754 это не обязательно “крах”, а определённый результат);
переполнение по диапазону (слишком большое по модулю число при округлении может стать бесконечностью).

Примеры типичных правил:

$1.0 / 0.0 = +\infty$ ;
$-1.0 / 0.0 = -\infty$ ;
$1.0 / (+\infty) = 0.0$ .

NaN (Not a Number)

Если экспонента вся из единиц, а дробь не нулевая ( $F \ne 0$ ), то это NaN.

NaN означает, что результат операции не является числом в привычном смысле.

Типичные источники NaN:

$0.0 / 0.0$ ;
$\infty - \infty$ ;
$\sqrt{-1}$ в вещественных числах.

Тихие и сигнальные NaN (важно концептуально)

В IEEE 754 различают:

quiet NaN (qNaN) — обычно «тихо распространяется» дальше по вычислениям;
signaling NaN (sNaN) — предназначен для сигнализации об ошибке (реакция зависит от системы и настроек).

В учебной практике главное запомнить:

NaN заражает вычисления: многие операции с NaN дают NaN;
сравнения с NaN ведут себя необычно.

Необычные (но стандартные) случаи: +0 и -0

IEEE 754 имеет два нуля:

$+0$ (бит знака 0, экспонента 0, дробь 0);
$-0$ (бит знака 1, экспонента 0, дробь 0).

Зачем это нужно:

для корректной обработки предельных переходов и знака результата в некоторых операциях;
чтобы, например, различать $1/(+0)=+\infty$ и $1/(-0)=-\infty$ .

При этом в большинстве “обычных” сравнений:

$+0 == -0$ считается истинным.

Как распознать класс числа по полям (быстрая памятка)

Пусть $E$ — поле экспоненты, $F$ — поле дроби.

Условие по полям	Класс значения
$E=0$ , $F=0$	$+0$ или $-0$ (по $s$ )
$E=0$ , $F\ne0$	subnormal
$0<E<\text{all-ones}$	normal
$E=\text{all-ones}$ , $F=0$	$+\infty$ или $-\infty$
$E=\text{all-ones}$ , $F\ne0$	NaN

Почему NaN «ломает» сравнения

NaN используют, чтобы не подменять ошибку каким-то “обычным числом” вроде 0.

Поэтому IEEE 754 задаёт правило:

любое сравнение вида $x == \text{NaN}$ ложно;
любое сравнение вида $x < \text{NaN}$ и $x > \text{NaN}$ тоже ложно;
при этом $x != \text{NaN}$ истинно для любого $x$ , включая сам NaN.

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

Сопоставление с фиксированной точкой: что стало проще и что сложнее

Что плавающая точка делает проще:

огромный динамический диапазон (очень большие и очень маленькие числа);
не нужно вручную выбирать единый масштаб $2^{-f}$ для всех значений.

Что становится сложнее:

точность неравномерна по диапазону (шаг между соседними числами зависит от величины);
появляются особые значения (NaN, $\pm\infty$ , $\pm0$ );
округление и режимы округления становятся центральной темой.

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

Источники для углубления

Арифметика и округления: ошибки, устойчивость, сравнение чисел

Зачем нужна эта тема

В предыдущих статьях курса мы разобрали, как числа кодируются:

целые в двоичном виде, включая дополнительный код и переполнение;
дробные в фиксированной точке, где масштаб задаётся вручную;
числа с плавающей точкой IEEE 754, где масштаб хранится в экспоненте и появляются особые значения вроде NaN и $\pm\infty$ .

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

В этой статье разберём:

откуда берутся ошибки округления и какие они бывают;
что такое абсолютная и относительная ошибка;
почему одни формулы вычисляются надёжно, а другие нет (устойчивость);
как правильно сравнивать числа с плавающей точкой;
что делать с NaN, бесконечностями и нулями IEEE 754 в логике программ.

Округление как неизбежность конечного формата

Что происходит при записи результата

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

Для IEEE 754 наиболее распространённый режим по умолчанию — округление к ближайшему, при равенстве к чётному (round to nearest, ties to even). Идея «к чётному» нужна, чтобы избежать систематического смещения при большом числе округлений.

Модель ошибки округления

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

\operatorname{fl}(x) = x(1+\delta)

Пояснение элементов формулы:

$x$ — точный (математический) результат;
$\operatorname{fl}(x)$ — результат после округления в формат (от слова floating);
$\delta$ — относительная ошибка округления; обычно она мала и ограничена некоторой константой, зависящей от формата и режима округления.

Важный смысл: ошибка часто относительная, то есть масштабируется вместе с числом. Поэтому абсолютная ошибка у больших чисел обычно больше.

Абсолютная и относительная ошибка

Пусть есть истинное значение $x$ и приближённое $\hat{x}$ .

Абсолютная ошибка

\Delta = |\hat{x} - x|

Пояснение:

$x$ — истинное значение;
$\hat{x}$ — вычисленное или представимое значение;
$|\cdot|$ — модуль;
$\Delta$ показывает «на сколько в абсолютных единицах» мы ошиблись.

Абсолютная ошибка полезна, когда известна физическая шкала: например, ошибка в метрах.

Относительная ошибка

\varepsilon = \frac{|\hat{x} - x|}{|x|}

Пояснение:

числитель $|\hat{x} - x|$ — абсолютная ошибка;
знаменатель $|x|$ — масштаб истинного значения;
$\varepsilon$ показывает, насколько ошибка велика по сравнению с самим числом.

Относительная ошибка удобна, когда важен процент или число значащих цифр. Но она плохо определена, если $x\approx 0$ (деление на очень маленькое число раздувает показатель).

ULP и машинный эпсилон

ULP

ULP (unit in the last place) — шаг между двумя соседними представимыми числами в конкретной области шкалы. В IEEE 754 этот шаг растёт с увеличением экспоненты: чем больше по модулю число, тем «реже сетка».

Практический смысл: ошибка «в 1 ULP» часто означает «округлено максимально аккуратно для данного формата», но абсолютный размер ULP зависит от величины числа.

Машинный эпсилон

Машинный эпсилон обычно понимают как расстояние между 1 и ближайшим числом больше 1 в данном формате.

для binary64 (double) это примерно $2^{-52}$ ;
для binary32 (float) это примерно $2^{-23}$ .

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

Важно: машинный эпсилон — это не «максимальная ошибка любых вычислений», а характеристика плотности представимых чисел около 1.

Типичные источники численных проблем

Катастрофическая потеря значимости

Самый известный случай — вычитание близких чисел:

если $a\approx b$ , то разность $a-b$ мала;
но в вычислении участвуют числа, у которых уже есть округления;
значащие биты результата могут «вымыться», и относительная ошибка результата резко возрастает.

Пример идеи без привязки к конкретным значениям:

было две величины с точностью до, скажем, 15 значащих цифр;
после вычитания почти равных чисел может остаться 2–3 значащих цифры.

Это не «баг IEEE 754», а математическое следствие: операция вычитания превращает относительную ошибку входов в большую относительную ошибку выхода.

Поглощение (absorption)

Если складывать очень большое и очень маленькое число, маленькое может не изменить сумму:

$x + y = x$ , если $y$ меньше половины ULP около $x$ .

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

Накопление ошибки

Округление происходит почти после каждой операции. Ошибки могут:

частично компенсироваться;
или накапливаться, если порядок действий неудачен.

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

Устойчивость алгоритмов

Важно различать:

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

Идея устойчивости в практических терминах

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

Эта формулировка полезна, потому что:

любое представление входа уже содержит округление;
«идеальной точности» всё равно нет.

Пример: суммирование многих чисел

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

Практические правила:

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

Один из известных приёмов — суммирование Кэхэна (Kahan summation): оно хранит компенсацию потерянной «мелочи» и уменьшает ошибку накопления.

Идея (в словах):
1) держим сумму s и компенсацию c
2) перед добавлением x вычитаем c, чтобы вернуть потерянные биты
3) после сложения обновляем c как то, что "съело" округление

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

Сравнение чисел с плавающей точкой

Почему `a == b` часто плохая идея

Из-за округлений выражения, которые математически равны, могут давать результаты, отличающиеся на малую величину.

Пример типовой ситуации:

вы вычисляете значение двумя способами (через разные формулы);
оба способа «правильные», но округления разные;
прямое сравнение на равенство возвращает ложь.

Сравнение с допуском

Обычно используют допуск.

Абсолютный допуск:

|a-b| \le \tau

Пояснение:

$a$ , $b$ — сравниваемые значения;
$|a-b|$ — их абсолютная разница;
$\tau$ — выбранный порог (например, допустимая физическая погрешность измерения).

Относительный допуск:

\frac{|a-b|}{\max(|a|,|b|)} \le r

Пояснение:

числитель $|a-b|$ — абсолютная разница;
знаменатель $\max(|a|,|b|)$ — масштаб сравниваемых значений (берём максимум, чтобы не делить на слишком маленькое);
$r$ — допустимая относительная ошибка.

На практике часто комбинируют оба:

абсолютный допуск важен около нуля;
относительный — на больших масштабах.

Важная оговорка про выбор допуска

Допуск нельзя выбирать «магически» одинаковым для всех задач. Его определяют:

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

Особые значения IEEE 754 в вычислениях и сравнениях

NaN

NaN распространяется через многие операции и «ломает» обычные сравнения:

$x == \text{NaN}$ — ложь для любого $x$ ;
$x < \text{NaN}$ и $x > \text{NaN}$ — тоже ложь;
$x != \text{NaN}$ — истина для любого $x$ , включая NaN.

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

Бесконечности

$+\infty$ и $-\infty$ ведут себя предсказуемо во многих операциях (например, сравнения с конечными числами), но требуют аккуратности в выражениях вида $\infty-\infty$ , которые дают NaN.

Два нуля

В IEEE 754 есть $+0$ и $-0$ . Обычно они равны в сравнении, но могут различаться в выражениях вида $1/(\pm 0)$ , давая $\pm\infty$ . Это полезно для корректной обработки предельных переходов.

Практические рекомендации

Избегайте вычитания близких чисел, если можно преобразовать формулу.
При суммировании большого количества чисел учитывайте порядок сложения; при необходимости используйте компенсированное суммирование.
Не сравнивайте числа с плавающей точкой через прямое равенство, кроме случаев, когда вы точно контролируете вычисления (например, сравнение с заранее записанной константой, которая получена тем же способом).
Для сравнения используйте абсолютный и относительный допуски.
Всегда продумывайте, что должно происходить при NaN и $\pm\infty$ в вашей логике.

Что дальше

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

Если углубляться далее, обычно рассматривают:

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

Источники для углубления

Алгоритмы численной обработки: суммы, фильтрация, нормализация

Связь с предыдущими темами курса

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

целые числа и переполнение (в том числе дополнительный код);
фиксированную точку и то, что масштаб приходится контролировать вручную;
IEEE 754 и особые значения вроде NaN и $\pm\infty$ ;
округления, ULP, поглощение, потерю значимости и то, почему сравнение a == b опасно.

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

Суммы: как получить точнее и надёжнее

Почему сумма — это не тривиально

Математически сложение ассоциативно: $(a+b)+c = a+(b+c)$ . На компьютере для чисел с плавающей точкой это часто не так, потому что после каждого сложения результат округляется в конечный формат.

На точность суммы влияют:

порядок сложения;
разный масштаб слагаемых;
наличие очень маленьких добавок к большой частичной сумме (поглощение);
переполнение (для целых и фиксированной точки) и выход за диапазон (для IEEE 754 с переходом в $\pm\infty$ ).

Базовая модель: сумма как алгоритм

Пусть есть числа $x_1, x_2, \dots, x_n$ . Сумма в математике:

S = \sum_{i=1}^{n} x_i

Пояснение элементов формулы:

$S$ — итоговая сумма;
$\sum$ — операция суммирования;
$i$ — индекс элемента;
$n$ — количество элементов;
$x_i$ — i-е слагаемое.

Компьютер же обычно делает так:

заводит переменную s = 0;
по очереди добавляет s = s + x[i].

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

Приём: суммирование от меньших по модулю к большим

Если вы можете отсортировать значения по возрастанию модуля, то часто становится лучше, потому что маленькие числа суммируются, пока частичная сумма ещё не слишком велика.

Ограничения:

сортировка стоит времени и памяти;
если данные потоковые (стрим), сортировать невозможно.

Приём: попарное (tree) суммирование

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

Практический эффект:

меньше накопление ошибки, чем при линейной схеме слева направо;
особенно полезно в параллельных вычислениях.

См. описание подхода: Pairwise summation.

Приём: компенсированное суммирование Кэхэна

Компенсированное суммирование хранит отдельную переменную-компенсацию потерянной «мелочи».

Интуиция:

при s + x часть значащих битов x может не попасть в результат из-за округления;
алгоритм пытается оценить эту потерю и добавить её позже.

Классический вариант (в псевдокоде):

s = 0
c = 0
for x in data:
  y = x - c
  t = s + y
  c = (t - s) - y
  s = t

Смысл переменных:

s — текущая сумма;
c — компенсация (то, что потерялось из-за округления);
y — скорректированная добавка;
t — промежуточная сумма.

Ссылка: Kahan summation algorithm.

Если данные целочисленные или фиксированная точка

Для целых и fixed-point главная опасность часто не округление, а переполнение.

Практические правила:

суммируйте в более широком типе (например, 16-битные значения складывать в 32-битный аккумулятор);
при fixed-point учитывайте масштаб: если $x = I / 2^f$ , то сумма кодов $I$ переполняется так же, как обычные целые;
если нужна предсказуемость, используйте насыщение (saturation), а не оборачивание.

Фильтрация: сглаживание и выделение полезного

Фильтрация — это преобразование последовательности чисел (сигнала) в другую последовательность, часто чтобы:

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

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

FIR-фильтры: конечная импульсная характеристика

Один из самых базовых вариантов — FIR (finite impulse response). Он вычисляет выход как взвешенную сумму нескольких последних входов.

Общее уравнение:

y[k] = \sum_{i=0}^{M-1} h[i] \cdot x[k-i]

Пояснение элементов формулы:

$x[\cdot]$ — входной сигнал;
$y[\cdot]$ — выходной сигнал;
$k$ — номер текущего отсчёта (текущий момент времени в дискретном сигнале);
$h[i]$ — коэффициенты фильтра (веса);
$M$ — число коэффициентов (длина фильтра);
$x[k-i]$ — i-й прошлый отсчёт.

Пример FIR, который знают почти все: скользящее среднее.

Скользящее среднее как фильтр

Если взять $M$ последних значений и усреднить, получится сглаживание.

y[k] = \frac{1}{M} \sum_{i=0}^{M-1} x[k-i]

Пояснение:

$M$ — размер окна усреднения;
$\frac{1}{M}$ — одинаковый вес каждого элемента;
остальное как в FIR.

Численные риски:

для целых и fixed-point сумма может переполниться, даже если результат после деления на $M$ помещается;
в float сумма больших и малых значений в окне может терять точность.

Ускорение (и иногда улучшение точности) для скользящего среднего:

хранить сумму окна sum;
на каждом шаге делать sum = sum + x_new - x_old.

Но здесь появляется другой риск: sum + x_new - x_old — это вычитание близких величин (особенно если сигнал стабильный), что может усиливать относительную ошибку. В float это обычно приемлемо при разумных масштабах, но в задачах высокой точности иногда предпочитают периодический пересчёт суммы окна заново.

Ссылки для ориентировки:

Convolution как универсальная форма FIR

FIR-фильтрация по сути является частным случаем свёртки (convolution) последовательностей.

Свёртка важна как концепция, потому что:

объясняет, почему FIR — это «взвешенная сумма соседей»;
помогает понимать, как меняется сигнал при разных $h[i]$ .

Ссылка: Convolution.

IIR-фильтры: бесконечная импульсная характеристика

IIR (infinite impulse response) добавляет обратную связь: выход зависит не только от входов, но и от прошлых выходов.

Общий вид разностного уравнения:

y[k] = \sum_{i=0}^{P} b[i] \cdot x[k-i] - \sum_{j=1}^{Q} a[j] \cdot y[k-j]

Пояснение элементов:

$b[i]$ — коэффициенты прямой части (вклад входов);
$a[j]$ — коэффициенты обратной связи (вклад прошлых выходов);
$P$ — глубина по входу;
$Q$ — глубина по выходу;
минус перед второй суммой — распространённая форма записи (зависит от соглашения).

Численные особенности IIR:

ошибки округления могут накапливаться из-за обратной связи;
в fixed-point очень важно иметь запас по диапазону (headroom), иначе насыщение или переполнение ломает динамику фильтра;
устойчивость фильтра зависит не только от математики коэффициентов, но и от реализации (структуры прямой формы, каскады бикуадов и т.д.).

Ссылка: Infinite impulse response.

Практика реализации фильтра: где прячутся ошибки

Типовые источники проблем:

коэффициенты фильтра записаны в float32, а не float64, и точности недостаточно;
при fixed-point не учтён масштаб коэффициентов и промежуточных произведений;
умножения делаются без расширения разрядности, и переполнение происходит до того, как вы «вернули» масштаб сдвигом;
NaN или $\pm\infty$ попали на вход (например, из деления на 0), и дальше «заражают» весь поток.

Минимальные меры предосторожности:

считать промежуточные суммы и произведения в более широком типе;
выбирать порядок суммирования коэффициентов (например, попарно);
явно определить политику обработки NaN/ $\pm\infty$ (пропуск, замена, останов).

Нормализация: приводим данные к удобному масштабу

Нормализация нужна, чтобы:

сделать числа сопоставимыми по масштабу;
улучшить обусловленность вычислений;
предотвратить переполнение в фиксированной точке;
стабилизировать обучение моделей и статистические методы;
сделать пороги и допуски осмысленными.

Важно: нормализация — это тоже арифметика (вычитания, деления, корни), значит она может порождать NaN, $\pm\infty$ и ошибки округления.

Min-max нормализация

Приводит данные к диапазону, например $[0,1]$ .

z = \frac{x - x_{\min}}{x_{\max} - x_{\min}}

Пояснение элементов:

$x$ — исходное значение;
$x_{\min}$ — минимум по выборке;
$x_{\max}$ — максимум по выборке;
$z$ — нормализованное значение.

Численные риски и проверки:

если $x_{\max} = x_{\min}$ , деление на 0 даёт NaN или $\pm\infty$ (в IEEE 754);
вычитание $x - x_{\min}$ может терять значимость, если значения очень близки, но обычно это терпимо, если затем делить на такой же небольшой диапазон.

Стандартизация (z-score)

Приводит данные к среднему 0 и стандартному отклонению 1.

z = \frac{x - \mu}{\sigma}

Пояснение:

$\mu$ — среднее значение по выборке;
$\sigma$ — стандартное отклонение;
$z$ — стандартизованное значение.

Численные акценты:

расчёт $\mu$ — это суммирование (применимы приёмы из начала статьи);
дисперсия и $\sigma$ требуют аккуратности из-за вычитания близких величин, поэтому на практике используют устойчивые алгоритмы (например, однопроходные варианты Уэлфорда).

Ссылки:

Нормализация по длине (L2-норма)

Часто встречается в геометрии, обработке признаков и сигналов: вектор приводится к длине 1.

Пусть $\mathbf{x} = (x_1, \dots, x_n)$ . Тогда:

\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^{n} x_i^2}

\mathbf{z} = \frac{\mathbf{x}}{\|\mathbf{x}\|_2}

Пояснение:

$\|\mathbf{x}\|_2$ — длина (евклидова норма) вектора;
$x_i^2$ — квадраты компонент;
корень делает итоговую величину сопоставимой с масштабом исходных компонент;
деление всех компонент на норму даёт вектор единичной длины.

Численные риски и типичный приём:

сумма квадратов может переполниться (в fixed-point и даже в float при очень больших значениях);
чтобы снизить риск, применяют масштабирование: выносят общий множитель, либо используют устойчивые реализации нормы.

Ссылка: Euclidean norm.

Как выбрать представление и масштаб в реальной системе

Если вы используете IEEE 754

Практические ориентиры:

чаще всего float64 даёт ощутимо более стабильные суммы и статистики, чем float32;
проверяйте и документируйте обработку NaN/ $\pm\infty$ на границах алгоритма;
сравнение результатов делайте с допуском (абсолютным и относительным), а не через ==.

Полезный обзор, почему это важно: What Every Computer Scientist Should Know About Floating-Point Arithmetic.

Если вы используете fixed-point

Нужно одновременно контролировать:

масштаб (сколько дробных битов $f$ в формате $I/2^f$ );
запас по диапазону (headroom) для промежуточных сумм;
стратегию переполнения: оборачивание или насыщение;
округление при сдвигах (усечение даёт систематическое смещение).

Практическая рекомендация уровня «чтобы работало»:

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

Итог: что вы должны уметь после этой темы

Объяснить, почему порядок суммирования влияет на результат в float.
Выбрать подход к суммированию: сортировка по модулю, попарное дерево, Кэхэн.
Понимать FIR как взвешенную сумму и уметь распознавать численные риски (переполнение суммы, накопление ошибки).
Понимать IIR как рекуррентную схему и почему обратная связь усиливает требования к точности.
Нормализовать данные и заранее предусмотреть крайние случаи: нулевой диапазон, нулевая дисперсия, нулевая норма.

Источники для углубления

Практика: выбор формата, тестирование и оптимизация вычислений

Как эта тема связывает весь курс

Ранее мы разобрали:

системы счисления и переводы между ними;
целые числа в двоичном виде, знаковые форматы и переполнение;
фиксированную точку как целое плюс масштаб;
IEEE 754: нормальные числа, subnormal, NaN, бесконечности, $\pm 0$ ;
округления, ULP, поглощение, потерю значимости и устойчивые приёмы суммирования;
базовые алгоритмы обработки: суммы, фильтрация, нормализация.

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

Выбор формата: как не ошибиться в самом начале

Выбор формата почти всегда определяет:

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

Что нужно собрать как требования

Полезно зафиксировать требования до выбора формата:

диапазон входов и выходов (минимум, максимум, типичные значения);
требуемая точность (в абсолютных единицах и относительно масштаба);
допустимы ли особые значения (NaN, $\pm \infty$ , $\pm 0$ ) или их нужно запрещать;
режим отказа при ошибке: оборачивание, насыщение, сигнализация, пропуск значения;
ограничения платформы (есть ли FPU, нужна ли строгая детерминированность, важна ли скорость).

Быстрая карта выбора

Вариант представления	Когда подходит	Главные риски	Типичные меры защиты
Целые (signed/unsigned)	счётчики, индексы, точные дискретные величины	переполнение, неверная интерпретация знака	более широкий аккумулятор, проверки границ, saturating-arithmetic
Фиксированная точка (fixed-point, $I/2^f$ )	сигналка, датчики, финальные форматы хранения, предсказуемость	переполнение промежуточных произведений, неверный масштаб, систематическое усечение	расширение разрядности, округление при сдвиге, насыщение, запас по диапазону
Плавающая точка (IEEE 754 float32)	много вычислений, важна скорость и память, точности достаточно	поглощение, потеря значимости, NaN в потоке	правильный порядок операций, допуски при сравнении, фильтрация NaN
Плавающая точка (IEEE 754 float64)	статистика, суммы, нормы, устойчивость важнее скорости	всё ещё есть округления, но меньше	те же приёмы, плюс контроль крайних случаев

Оценка диапазона и точности: практическая логика

Для целых чисел:

диапазон в $n$ битах ограничен (для знаковых two’s complement: от $-2^{n-1}$ до $2^{n-1}-1$ );
если сумма или произведение может выйти за диапазон, нужно либо расширять тип, либо менять алгоритм.

Для фиксированной точки (fixed-point):

Вы выбираете число дробных битов $f$ и храните целое $I$ , а реальное значение вычисляется по формуле:

x = \frac{I}{2^f}

Где:

$x$ — значение в привычном смысле;
$I$ — то, что реально лежит в памяти как целое;
$f$ — задаёт масштаб: чем больше $f$ , тем меньше шаг и тем меньше диапазон;
$2^f$ — делитель, который переводит целое обратно в дробное.

Практический вывод: точность задаётся шагом $\Delta = 2^{-f}$ . Переполнение происходит на уровне операций над $I$ , поэтому промежуточные вычисления почти всегда делают в более широком типе.

Для плавающей точки (IEEE 754):

точность неравномерна: шаг между числами растёт с масштабом;
важны особые значения (NaN, $\pm \infty$ , $\pm 0$ ) и правила сравнения.

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

Мини-кейс: скользящее среднее

Если нужно скользящее среднее по окну размера $M$ :

в float32 это часто нормально, но порядок операций и поглощение могут влиять;
в fixed-point опасно, что сумма окна переполнится до деления.

Практика для fixed-point:

Копить сумму окна в расширенном аккумуляторе (например, 16-битные отсчёты суммировать в 32 бита).
Делить с округлением.
Если система требует предсказуемых границ, применять насыщение.

Тестирование численных вычислений: что именно проверять

Тестирование численных вычислений отличается от обычного тем, что:

равенство a == b часто не является корректной проверкой;
множество ошибок проявляется только на краях диапазона или на специальных значениях;
разные платформы и компиляторы могут менять порядок вычислений и получать чуть разные результаты.

Что считать эталоном

Варианты эталона (reference) зависят от задачи:

вычисление в более точном типе (например, тестируем float32 через float64);
вычисление в целых с точным масштабом (когда это возможно);
независимая реализация другим способом (например, другая формула, другой порядок суммирования);
высокоточная библиотека (когда требуется).

Сравнение результатов: допуски вместо равенства

Часто используют комбинированный критерий с допусками:

|a-b| \le \tau + r \cdot \max(|a|,|b|)

Где:

$a$ и $b$ — сравниваемые значения;
$|a-b|$ — абсолютная разница;
$\tau$ — абсолютный допуск (важен около нуля);
$r$ — относительный допуск (важен на больших масштабах);
$\max(|a|,|b|)$ — задаёт характерный масштаб, чтобы не делить на очень маленькое число.

Практический смысл: если числа около нуля, главным становится $\tau$ . Если числа большие, главным становится относительный член с $r$ .

Если вы тестируете алгоритмы, чувствительные к округлению, полезно также измерять ошибку в ULP (Unit in the Last Place), но это уже более низкоуровневая техника.

Крайние случаи: обязательный чек-лист

Для целых и fixed-point:

максимум и минимум представимого значения;
значения около переполнения при сложении и умножении;
политика переполнения: оборачивание или насыщение;
расширение знака при приведении типов.

Для IEEE 754:

$+0$ и $-0$ ;
денормалы (subnormal — очень маленькие по модулю значения);
$+\infty$ и $-\infty$ ;
NaN (и проверка, что он не ломает ветвления и сравнения).

Свойства вместо конкретных чисел

Часто полезнее проверять свойства (property-based тестирование), чем фиксированные примеры:

монотонность: если вход растёт, выход не должен уменьшаться;
ограниченность: выход всегда в диапазоне;
симметрия: $f(-x)$ связано с $f(x)$ ожидаемым образом;
инварианты: например, после нормализации $\|z\|_2 \approx 1$ .

Свойства помогают ловить ошибки масштабирования в fixed-point и ошибки обработки NaN или бесконечностей в float.

Оптимизация вычислений: как ускорять и не испортить результат

Оптимизация вычислений почти всегда меняет хотя бы один из пунктов:

порядок операций;
точность промежуточных значений;
поведение на краях (переполнение, NaN, денормалы).

Поэтому правило практики:

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

Оптимизация порядка операций

То, что математически эквивалентно, вычислительно может быть разным. Примеры практичных замен:

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

Ускорение фильтров и свёрток

Типовые ускорения:

переиспользовать частичные суммы (для скользящего среднего);
применять SIMD-векторизацию, если данные упакованы;
для fixed-point хранить коэффициенты в удобном формате Q и умножать с расширением разрядности.

Но есть численные последствия. Переиспользование суммы окна делает шаг sum = sum + x_new - x_old, а это может усиливать чувствительность к округлению в float. SIMD и параллельное суммирование часто меняют порядок сложения, значит результат может отличаться в последних битах.

Использование FMA: быстрее и иногда точнее

На многих платформах есть операция умножить и прибавить с одним округлением — FMA (Fused Multiply-Add).

Практический эффект:

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

Риск практики: результаты могут отличаться от платформ, где FMA нет, что важно для строгой воспроизводимости.

Управление денормалами и производительностью

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

Практические подходы зависят от области:

в научных расчётах обычно сохраняют корректное IEEE 754 поведение;
в обработке сигналов иногда применяют режимы flush-to-zero (сброс в ноль), чтобы ускорить вычисления, но это меняет поведение около нуля.

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

Fixed-point: оптимизация через сдвиги и насыщение

Fixed-point часто выбирают именно ради скорости и детерминизма. Три практических правила, которые одновременно про корректность и скорость:

умножение делать в расширенном типе, затем применять сдвиг вправо на $f$ ;
при сдвиге вправо по возможности делать округление, а не усечение;
переполнение обрабатывать насыщением, если алгоритм не должен "оборачиваться".

Итоговый рабочий процесс

Надёжный процесс для численного фрагмента (функции, фильтра, нормализации) можно описать так:

Определить диапазоны входов и выходов.
Выбрать формат (int, fixed-point, float32, float64) по диапазону, точности и ограничениям платформы.
Определить политику краёв: переполнение, NaN, бесконечности, $\pm 0$ .
Написать эталон или метод проверки (более точный расчёт, независимая реализация).
Построить тесты с допусками и покрытием крайних случаев.
Профилировать.
Оптимизировать (порядок операций, SIMD, FMA, масштабирование).
Повторно прогнать тесты и зафиксировать ожидаемые допустимые расхождения.

Источники для углубления

Итоги

Выбор числового формата (int, fixed-point, float) определяет баланс между точностью, диапазоном и производительностью.
Тестирование вычислений требует использования допусков (абсолютных и относительных) вместо строгого равенства, а также обязательной проверки крайних случаев (NaN, $\pm \infty$ , переполнения).
Оптимизация (изменение порядка операций, SIMD, FMA) может изменить итоговый результат, поэтому её следует проводить только после написания тестов и профилирования.