Двоичное кодирование

В информационных системах для двоичной записи целых чисел обычно используют фиксированное число двоичных разрядов (позиций для двоичных цифр) n. Если число имеет в своей записи m≤n двоичных цифр, в первые n−m позиций вписываются нули, а в оставшиеся m позиций цифры числа. Таким образом, используя n двоичных разрядов, можно представить все числа от 0 до 2ⁿ−1.

Всякое сообщение, записанное с использованием символов некоторого алфавита, можно представить в виде некоторой последовательности из нулей и единиц. В самом деле, пусть A={a,b,…} – конечный алфавит. Выберем число n так, чтобы 2ⁿ было не меньше, чем число его символов. Перенумеруем символы алфавита (начиная нумерацию с нуля) и припишем каждому из них его двоичный код – двоичную запись номера символа с использованием n двоичных разрядов (битов). Текст ab…, представляется последовательностью блоков

α_n−1α_n−2…α₁α₀β_n−1β_n−2…β₁β₀…,

где α_n−1α_n−2…α₁α₀ – двоичная запись номера символа a, β_n−1β_n−2…β₁β₀ – двоичная запись номера символа b, и т.д.

В информатике распространены системы кодирования символов алфавита с использованием 8-разрядных блоков – байтов. Это позволяет работать с алфавитами, содержащими до 256 символов. Обычно используемые алфавиты содержат латинские буквы, буквы национального алфавита, цифры, знаки препинания и некоторые специальные знаки.

6.2. Векторное пространство {0,1}ⁿ

На множестве n-мерных двоичных векторов определим операцию ⊕ – сложение по модулю 2. Сумма двоичных векторов α=(α₁,α₂,…,α_n) и β=(β₁,β₂,…,β_n) определяется формулой

α⊕β = (α₁⊕β₁, α₁⊕β₁,…, α_n⊕β_n).

Вектор α⊕β содержит единицы на тех местах, где координаты векторов α и β различаются, и нули – на тех, где совпадают.

Примеры. (0,1,0,1)⊕(0,0,1,1) = (0,1,1,0);

(0,1,0,1)⊕(1,1,1,1) = (1,0,1,0);

(0,1,0,1)⊕(0,1,0,1) = (0,0,0,0).􀀀

Операция ⊕ обладает важными свойствами обычного сложения: она коммутативна и ассоциативна, нулевой вектор является нейтральным элементом. Кроме того, α⊕α является нулевым вектором для любого вектора α.

Система n-мерных двоичных векторов линейно зависима, если сумма (по модулю 2) нескольких векторов из этой системы равна 0 (мы используем один и тот же символ «0» для обозначения числа «ноль» и нулевого вектора, когда из контекста ясно, о чем идет речь). На двоичные векторы распространяются стандартные свойства линейной зависимости:

в пространстве {0,1}ⁿ любая система, содержащая более n векторов, линейно зависима;

любые n линейно независимых векторов образуют базис пространства {0,1}ⁿ; всякий вектор из {0,1}ⁿ может быть единственным образом представлен в виде суммы нескольких базисных векторов.

Двоичные векторы (0,0,…,0,1), (0,0,…,1,0),…, (1,0,…,0,0) образуют базис пространства {0,1}ⁿ, называемый каноническим.

Число единичных координат двоичного вектора α=(α₁,α₂,…,α_n) обозначают через w(α) и называют весом вектора α. Очевидно,

w(α) = α₁+α₂+…+α_n.

Формулой

d(α,β) = w(α⊕β)

определяется расстояние d(α,β) между двоичными векторами α и β, называемое расстоянием Хемминга. Расстояние Хемминга обладает следующими свойствами:

1) d(α,α)=0 и d(α,β)>0 при α≠β;

2) d(α,β)=d(β,α);

3) d(α,β)+d(β,γ)≥d(α,γ) (неравенство треугольника).

6.3. Отображения {0,1}ⁿ в {0,1}^m

Произвольное отображение из {0,1}ⁿ в {0,1}^m, (x₁,x₂,…,x_n) → (y₁,y₂,…,y_m),

задается набором булевых функций

y₁=f₁(x₁,x₂,…,x_n), y₂=f₂(x₁,x₂,…,x_n), …, y_m=f_m(x₁,x₂,…,x_n).

Чтобы задать такое отображение, требуется указать m двоичных векторов размерности 2ⁿ. Таким образом, для задания произвольного отображения необходимо m×2ⁿ бит информации. Например, отображение из {0,1}² в {0,1}³ задается вектором размерности 12 (составленным из трех векторов размерности 4). Общее число отображений из {0,1}² в {0,1}³ равно 2¹²=4096.

Напомним, что линейной называется функция вида

f(x₁,x₂,…,x_n) = c₁x₁ ⊕ c₂x₂ ⊕ … ⊕ c_nx_n,

где c=(c₁,c₂,…,c_n) – произвольный двоичный вектор.

Булева функция f:{0,1}ⁿ → {0,1} является линейной, если

f(α⊕β)=f(α)⊕f(β)

для любых α и β из {0,1}ⁿ.

В самом деле, так как

(x₁,x₂,…,x_n) = x₁⋅(1,0,…,0) ⊕ x₂⋅(0,1,…,0)⊕…⊕ x_n⋅(0,0,…,1),

то

f(x₁,x₂,…,x_n) = x₁⋅f(1,0,…,0) ⊕ x₂⋅f(0,1,…,0)⊕…⊕ x_n⋅f(0,0,…,1).

Вектор c=(c₁,c₂,…,c_n) имеет следующий вид:

c₁ = f(1,0,…,0), c₂= f(0,1,…,0), …, c_n= f(0,0,…,1).

Общее число линейных функций от n переменных равно числу n-мерных двоичных векторов, то есть равно 2ⁿ. Как видно из предыдущего, линейная функция f является суммой нескольких своих аргументов. Например, x₁ входит слагаемым в эту сумму, если f(1,0,…,0)=1, и не входит, если f(1,0,…,0)=0.

Пример. Перечислим все линейные функции y=f(x₁,x₂,x₃) от трех переменных:

y=0 (тождественный 0); y=x₁; y=x₂; y=x₃;

y=x₁⊕x₂; y=x₁⊕x₃; y=x₂⊕x₃; y=x₁⊕x₂⊕x₃.􀀀

Отображение f:{0,1}ⁿ → {0,1}^m называется линейным, если f(α⊕β)=f(α)⊕f(β) для любых α и β из {0,1}ⁿ. Отображение

f:{0,1}ⁿ → {0,1}^m , (x₁,x₂,…,x_n) → (y₁,y₂,…,y_m),

линейно тогда и только тогда, когда линейны все его компоненты

y₁=f₁(x₁,x₂,…,x_n), y₂=f₂(x₁,x₂,…,x_n),…, y_m=f_m(x₁,x₂,…,x_n).

Отсюда следует, что линейное отображение из {0,1}ⁿ в {0,1}^m однозначно определяется набором, содержащим m двоичных векторов размерности n, то есть некоторой матрицей из нулей и единиц размера m×n. Для задания линейного отображения необходимо m×n бит информации. Общее число линейных функций из {0,1}ⁿ в {0,1}^m равно 2^mn.

Пример. Рассмотрим линейное отображение f из {0,1}² в {0,1}³. Задать его можно, указав матрицу из нулей и единиц (c_ij), i=1,2,3, j=1,2:

y₁=c₁₁x₁⊕c₁₂x₂, y₂=c₂₁x₁⊕c₂₂x₂, y₃=c₃₁x₁⊕c₃₂x₂.

Пусть, например,

y₁=x₁, y₂=x₂, y₃=x₁⊕x₂.

Тогда

c₁₁=1, c₁₂=0, c₂₁=0, c₂₂=1, c₃₁=1, c₃₂=1.􀀀

Следующая таблица дает некоторое представление о росте объема информации, необходимой для задания произвольных и линейных отображений из {0,1}ⁿ в {0,1}^m.

Задание отображения из {0,1}ⁿ в {0,1}^m (бит)

n m произвольное линейное

1 1 2 1

1 2 4 2

2 2 8 4

2 3 12 6

3 4 32 12

8 9 2304 72

15 20 655360 300

Не нашли, что искали? Воспользуйтесь поиском: