Информатика
Кодирование информации
Формулы для битов, байтов, алфавитов, сообщений и передачи данных.
48 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Количество информации по алфавитному подходу | $I = K \cdot i$ | Кодирование информации | Количество информации по алфавитному подходу равно числу символов сообщения, умноженному на информационный вес одного символа в битах. |
| Мощность алфавита | $N = 2^i$ | Кодирование информации | Мощность алфавита N=2^i показывает, сколько различных символов можно закодировать, если на один символ отводится ровно i бит. |
| Количество наборов битовой строки | $N = 2^n$ | Системы счисления | Количество наборов битовой строки длины n равно 2^n, потому что каждая позиция независимо принимает одно из двух значений: 0 или 1. |
| Перевод двоичного числа в десятичное по разрядам | $N_{10}=\sum b_i 2^i$ | Системы счисления | Перевод двоичного числа в десятичное по разрядам: формула N_{10}=\sum b_i 2^i помогает величины N, b_i, i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Перевод десятичного числа в двоичное делением с остатками | $N=\sum r_i 2^i$ | Системы счисления | Перевод десятичного числа в двоичное делением с остатками: формула N=\sum r_i 2^i помогает величины N, r_i, i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Перевод десятичного числа в шестнадцатеричное | $N=\sum h_i 16^i$ | Системы счисления | Перевод десятичного числа в шестнадцатеричное: формула N=\sum h_i 16^i помогает величины N, h_i, i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Сложение двоичных чисел с переносом | $0+0=0,\ 1+1=10_2$ | Системы счисления | Сложение двоичных чисел с переносом: формула 0+0=0,\ 1+1=10_2 помогает требуется требуется требуется требуется требуется требуется сложить два двоичных числа и правильно перенести единицу в следующий разряд. В тексте есть условия, пример, ошибки и проверка результата. |
| Отрицательное целое число в дополнительном коде | $x_{code}=2^n-|x|$ | Системы счисления | Отрицательное целое число в дополнительном коде: формула x_{code}=2^n-|x| помогает требуется требуется требуется требуется требуется требуется записать отрицательное число в n-битном дополнительном коде. В тексте есть условия, пример, ошибки и проверка результата. |
| Сколько бит нужно для кодирования N значений | $k=\lceil \log_2 N\rceil$ | Системы счисления | Сколько бит нужно для кодирования N значений: формула k=\lceil \log_2 N\rceil помогает требуется требуется требуется требуется требуется требуется определить минимальную длину кода для набора вариантов. В тексте есть условия, пример, ошибки и проверка результата. |
| Информационный объем сообщения по мощности алфавита | $I=K\cdot \lceil\log_2 q\rceil$ | Объём цифровых данных | Информационный объем сообщения по мощности алфавита: формула I=K\cdot \lceil\log_2 q\rceil помогает величины I, K, q заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Размер растрового изображения по пикселям и глубине цвета | $I=W\cdot H\cdot b$ | Объём цифровых данных | Размер растрового изображения по пикселям и глубине цвета: формула I=W\cdot H\cdot b помогает величины I, W, H, b заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Размер аудиофайла по частоте дискретизации | $I=f\cdot t\cdot b\cdot c$ | Объём цифровых данных | Размер аудиофайла по частоте дискретизации: формула I=f\cdot t\cdot b\cdot c помогает величины I, f, t, b заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Таблица истинности логического выражения | $2^n\ \text{строк}$ | Логика | Таблица истинности логического выражения: формула 2^n\ \text{строк} помогает требуется требуется требуется требуется требуется требуется понять, сколько строк строить и как проверить все наборы истинности. В тексте есть условия, пример, ошибки и проверка результата. |
| Отрицание конъюнкции и дизъюнкции | $\neg(A\land B)=\neg A\lor\neg B$ | Логика | Отрицание конъюнкции и дизъюнкции: формула \neg(A\land B)=\neg A\lor\neg B помогает величины A, B заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Импликация в логическом выражении | $A\to B\equiv \neg A\lor B$ | Логика | Импликация в логическом выражении: формула A\to B\equiv \neg A\lor B помогает величины A, B заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Эквиваленция двух логических высказываний | $A\leftrightarrow B\equiv (A\land B)\lor(\neg A\land\neg B)$ | Логика | Эквиваленция двух логических высказываний: формула A\leftrightarrow B\equiv (A\land B)\lor(\neg A\land\neg B) помогает величины A, B заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Законы де Моргана для логических условий | $\neg(A\lor B)=\neg A\land\neg B$ | Логика | Законы де Моргана для логических условий: формула \neg(A\lor B)=\neg A\land\neg B помогает требуется требуется требуется требуется требуется требуется раскрыть отрицание условия с И или ИЛИ без ошибки со знаками. В тексте есть условия, пример, ошибки и проверка результата. |
| Число наборов, при которых логическое выражение истинно | $M=\#\{x:F(x)=1\}$ | Логика | Число наборов, при которых логическое выражение истинно: формула M=\#\{x:F(x)=1\} помогает требуется требуется требуется требуется требуется требуется посчитать подходящие наборы переменных для условия из задания. В тексте есть условия, пример, ошибки и проверка результата. |
| Число адресов хостов по длине маски | $H=2^{32-m}-2$ | Адресация и передача данных | Число адресов хостов по длине маски: формула H=2^{32-m}-2 помогает величины H, m заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Количество подсетей по числу заимствованных битов | $S=2^b$ | Адресация и передача данных | Количество подсетей по числу заимствованных битов: формула S=2^b помогает величины S, b заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Расстояние Хэмминга между двоичными словами | $d(x,y)=\sum [x_i\ne y_i]$ | Кодирование информации | Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Время передачи файла по скорости канала | $t=\frac{I}{v}$ | Адресация и передача данных | Время передачи файла по скорости канала: формула t=\frac{I}{v} помогает величины t, I, v заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата. |
| Индекс Жаккара: сходство через пересечение множеств | $J(A,B)=\frac{|A\cap B|}{|A\cup B|}$ | Алгоритмы и анализ данных | Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств. |
| Косинусное сходство векторов: формула и расчёт угла | $\cos\theta=\frac{a\cdot b}{\lVert a\rVert\,\lVert b\rVert}$ | Алгоритмы и анализ данных | Косинусное сходство сравнивает направление двух ненулевых векторов и принимает значения от −1 до 1. Для неотрицательных векторов оно показывает, насколько совпадает профиль признаков. |
| Расстояние Левенштейна: вставки, удаления и замены | $D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}$ | Алгоритмы и анализ данных | Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается. |
| Неравенство Крафта: длины двоичных префиксных кодов | $\sum_{i=1}^{m}2^{-l_i}\le 1$ | Кодирование информации | Неравенство Крафта проверяет, могут ли заданные длины двоичных слов образовать префиксный код: сумма 2 в степени минус длина не должна превышать единицу. |
| Двоичный поиск: максимальное число сравнений ключа | $C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$ | Алгоритмы и анализ данных | Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций. |
| Энтропия Шеннона: средняя информация дискретного источника | $H(X)=-\sum_{i=1}^{m}p_i\log_2p_i$ | Кодирование информации | Энтропия Шеннона измеряет среднюю неопределённость исхода по его вероятностям. При двоичном логарифме результат выражают в битах на символ; редкие и частые символы вносят разный вклад. |
| Средняя длина кода Хаффмана: расход бит на символ | $\overline{L}=\sum_{i=1}^{m}p_i\ell_i$ | Кодирование информации | Средняя длина двоичного кода равна сумме длин кодовых слов с весами вероятностей символов. Для кода Хаффмана этот расход минимален среди двоичных посимвольных префиксных кодов с заданными вероятностями. |
| Минимальное расстояние кода: сколько ошибок можно исправить | $t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$ | Кодирование информации | Минимальное расстояние между разрешёнными кодовыми словами определяет гарантированное число исправляемых замен битов. Чтобы исправить любые t ошибок, нужно расстояние не меньше 2t+1. |
| Граница Хэмминга: сколько слов помещается в исправляющий код | $M\sum_{j=0}^{t}\binom{n}{j}\le 2^n$ | Кодирование информации | Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений. |
| Закон Амдала: предел ускорения параллельной программы | $S(N)=\frac{1}{(1-p)+p/N}$ | Алгоритмы и анализ данных | Закон Амдала оценивает ускорение неизменной задачи на N одинаковых исполнителях, если долю p исходного времени можно идеально распараллелить. Последовательная часть ограничивает итоговый выигрыш. |
| Дискретное преобразование Фурье и обратная формула | $X_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i kn/N},\qquad x_n=\frac1N\sum_{k=0}^{N-1}X_k e^{2\pi i kn/N}$ | Цифровая обработка сигналов | Дискретное преобразование Фурье переводит конечную последовательность в комплексные частотные коэффициенты. Обратная сумма восстанавливает все отсчёты; знак экспоненты и нормировку нужно выбирать согласованно. |
| Частоты и амплитуды по коэффициентам ДПФ | $\Delta f=\frac{f_s}{N},\quad f_k=\frac{kf_s}{N},\quad A_k=\frac{2|X_k|}{N}\quad(0<k<N/2)$ | Цифровая обработка сигналов | Шаг частот ДПФ равен частоте дискретизации, делённой на длину записи. Для вещественной гармоники точно на внутреннем частотном отсчёте амплитуда равна удвоенному модулю коэффициента, делённому на число отсчётов. |
| Наложение частот: расчёт алиаса при дискретизации | $f_a=\min_{m\in\mathbb Z}|f-mf_s|,\qquad 0\le f_a\le f_s/2$ | Цифровая обработка сигналов | При равномерной дискретизации вещественного гармонического сигнала частоты, отличающиеся на целое число частот дискретизации и знак, могут давать одинаковые отсчёты. Частота алиаса лежит от нуля до половины частоты дискретизации. |
| Линейная свёртка конечных последовательностей | $y_n=\sum_{k=-\infty}^{\infty}x_k h_{n-k},\qquad L_y=L_x+L_h-1$ | Цифровая обработка сигналов | Линейная свёртка складывает сдвинутые копии одной последовательности с весами другой. Для конечных массивов, продолженных нулями, полный результат содержит сумму их длин минус один отсчёт. |
| Окно Ханна: коэффициенты и поправка амплитуды | $w_n=\frac12\left(1-\cos\frac{2\pi n}{N-1}\right),\quad G_c=\frac1N\sum_{n=0}^{N-1}w_n,\quad N>1$ | Цифровая обработка сигналов | Симметричное окно Ханна плавно уменьшает края записи до нуля. Оно снижает дальнюю спектральную утечку ценой расширения главного лепестка и изменения амплитуды, поэтому масштаб спектра требует отдельной поправки. |
| Дивергенция Кульбака—Лейблера для дискретных распределений | $D_{KL}(P\|Q)=\sum_i p_i\log_2\frac{p_i}{q_i}$ | Кодирование информации | Дивергенция Кульбака—Лейблера для дискретных распределений даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации. |
| Взаимная информация двух дискретных величин | $I(X;Y)=\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}$ | Кодирование информации | Взаимная информация двух дискретных величин даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации. |
| Ёмкость двоичного симметричного канала | $C=1-H_2(p),\quad H_2(p)=-p\log_2p-(1-p)\log_2(1-p)$ | Кодирование информации | Ёмкость двоичного симметричного канала даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации. |
| Перекрёстная энтропия дискретного распределения | $H(P,Q)=-\sum_i p_i\log_2q_i$ | Кодирование информации | Перекрёстная энтропия дискретного распределения даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации. |
| Неравенство Фано: связь ошибки и условной энтропии | $H(X|Y)\le h_2(P_e)+P_e\log_2(|\mathcal X|-1)$ | Кодирование информации | Неравенство Фано сверху оценивает условную энтропию дискретного X через вероятность ошибки декодера X-hat=g(Y). Оно формализует: если X почти удаётся восстановить из наблюдения Y, неопределённость H(X|Y) не может быть большой. |
| Функция скорость—искажение для гауссовского источника | $R(D)=\max\left\{0,\frac12\log_2\frac{\sigma^2}{D}\right\},\quad D>0$ | Кодирование информации | Для независимого гауссовского источника с дисперсией sigma² и средней квадратичной ошибкой D функция скорость—искажение задаёт минимальную асимптотическую скорость кодирования: R(D)=max{0, 1/2 log_2(sigma²/D)} бит на отсчёт. |
| Пропускная способность двоичного канала со стиранием | $C_{\mathrm{BEC}}=1-\varepsilon$ | Кодирование информации | Пропускная способность двоичного канала со стиранием равна доле нестёртых символов. Она задаёт предельную скорость надёжной передачи в битах на одно использование канала. |
| Поляризация двоичного канала со стиранием | $\varepsilon_{-}=2\varepsilon-\varepsilon^2,\qquad \varepsilon_{+}=\varepsilon^2$ | Кодирование информации | Один шаг поляризации преобразует два независимых двоичных канала со стиранием в два битовых канала с разной надёжностью. У одного вероятность стирания растёт, у другого падает. |
| Условная энтропия дискретных случайных величин | $H(X\mid Y)=-\sum_{x,y:p(x,y)>0}p(x,y)\log_2 p(x\mid y)$ | Кодирование информации | Условная энтропия показывает, какая средняя неопределённость о X остаётся после наблюдения Y. Она усредняет энтропии условных распределений с учётом вероятностей наблюдений. |
| Энтропия Реньи: порядок и вероятность совпадения | $H_\alpha(P)=\frac{1}{1-\alpha}\log_2\sum_i p_i^\alpha,\qquad \alpha>0,\quad\alpha\ne1$ | Кодирование информации | Энтропия Реньи — семейство мер неопределённости с параметром порядка α. При α=2 она определяется вероятностью совпадения двух независимых выборок из одного распределения. |
| Расстояние полной вариации дискретных распределений | $d_{\mathrm{TV}}(P,Q)=\frac12\sum_i|p_i-q_i|=\max_A|P(A)-Q(A)|$ | Статистические выводы | Расстояние полной вариации равно наибольшему расхождению вероятностей одного события по двум распределениям. Для конечного алфавита его считают как половину суммы модулей разностей. |