Информатика

Кодирование информации

Формулы для битов, байтов, алфавитов, сообщений и передачи данных.

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)|$ Статистические выводы Расстояние полной вариации равно наибольшему расхождению вероятностей одного события по двум распределениям. Для конечного алфавита его считают как половину суммы модулей разностей.