Инструменты сайта


§

Вспомогательная страница к разделу ЛИНЕЙНОЕ ПРОСТРАНСТВО. Применение ТЕОРИЯ КОДИРОВАНИЯ


Линейные пространства над конечными полями

Здесь мы сравним свойства линейных пространств с конечным и бесконечным числом элементов.

Поле из двух элементов

Будем рассматривать упорядоченные наборы — строки1) $ (x_1,\dots,x_{n}) $ из $ n_{} $ чисел $ \{x_1,\dots,x_n\}\subset \{0,1\} $. Множество таких наборов, рассматриваемое вместе с операцией умножения на константы $ 0_{} $ или $ 1_{} $ и операцией поразрядного сложения по модулю $ 2_{} $: $$ (x_1,\dots,x_n)+(y_1,\dots,y_n)=(x_1+y_1 \pmod{2},\dots,x_n+y_n \pmod{2}) $$ образует линейное пространство, которое мы будем обозначать $ \mathbb V^n $, а собственно составляющие его наборы будем называть векторами.

Строго говоря, надо было бы говорить о векторах, элементами которых являются классы вычетов по модулю $ 2_{} $, но я не буду заморачиваться излишним формализмом.

Свойства.

1. Это пространство состоит из конечного числа векторов2): $ \operatorname{Card} (\mathbb V^n)=2^n $.

2. Любой вектор $ X\in \mathbb V^n $ является обратным самому себе: $$ X+X=2\,X \equiv \mathbb O \pmod{2} \qquad \Rightarrow \qquad -X=X \ . $$

3. Два вектора $ \{X,Y\}\subset \mathbb V^n $ линейно независимы тогда и только тогда, когда они различны (различаются хотя бы по одной координате).

4. Размерность пространства $ \mathbb V^n $ равна $ n_{} $: $ \dim V^n = n_{} $; в качестве базиса можно взять строки $$ \mathfrak e_j = \overbrace{[\underbrace{0,\dots,0,1}_j,0,\dots \,0]}^n \quad npu \ j \in \{1,\dots,n\} \ . $$

5. Если скалярное произведение в $ \mathbb V^n $ определить по аналогии с $ \mathbb R^{3} $: $$ \langle (x_1,\dots,x_n),(y_1,\dots,y_n)\rangle =x_1y_1+\dots+x_ny_n \pmod{2} \ , $$ то существуют ненулевые векторы $ X\in \mathbb V^n $, ортогональные самим себе: $$ \langle (1,1,0), (1,1,0) \rangle =2 \equiv 0 \pmod{2} \ . $$

6. Пусть теперь во множестве $ \mathbb V^n $ определена операция умножения элементов по правилу, изложенному ЗДЕСЬ. Для векторов $$ \mathfrak a=(a_0,a_1,\dots,a_{n-1}) \quad \mbox{ и } \quad \mathfrak b=(b_0,b_1,\dots,b_{n-1}) $$ их произведение определяется как элемент $$ \mathfrak c=(c_0,c_1,\dots,c_{n-1}) , $$ такой, что $$ c_0x^{n-1}+c_1x^{n-2}+\dots+c_{n-1} \equiv $$ $$ \equiv (a_0x^{n-1}+a_1x^{n-2}+\dots+a_{n-1})(b_0x^{n-1}+b_1x^{n-2}+\dots+b_{n-1}) \quad (\operatorname{modd} \ 2,f(x)) ; $$ что означает: после выполнения умножения полиномов, мы вычисляем остаток этого произведения при делении его на некоторый полином $ f_{}(x) $ степени $ n_{} $ с коэффициентами из $ \{0,1\} $ , и, вдобавок, неприводимый над $ \mathbf{GF}(2) $; коэффициенты остатка приводятся по модулю $ 2_{} $. Иными словами из линейного пространства $ \mathbb V^n $ сделали поле Галуа $ \mathbf{GF}(2^n) $. Существует элемент $ \mathfrak a_{} $ поля $ \mathbf{GF}(2^n) $ такой, что элементы поля $$ \mathfrak a, \mathfrak a^2, \mathfrak a^4,\dots, \mathfrak a^{2^{n-1}} $$ (каждый следующий является квадратом предыдущего) образуют базис пространства $ \mathbb V^n $. Любой такой базис называется нормальным базисом.

П

Пример. Для поля $ \mathbf{GF}(2^4) $, порожденному полиномом $ f(x)=x^4+x+1 $ элемент $ \mathfrak a = (1,0,0,0) $ порождает нормальный базис. Действительно, указанному элементу соответствует полином $ x^3 $ и

$$ \left(x^3\right)^2=x^6 \equiv x^3+x^2 \quad (\operatorname{modd} \ 2,f(x)), $$ $$(x^3+x^2)^2 \equiv x^6+x^4 \equiv x^3+x^2+x+1 \quad (\operatorname{modd} \ 2,f(x)), $$ $$ (x^3+x^2+x+1)^2 \equiv x^3+x \quad (\operatorname{modd} \ 2,f(x)) \ . $$ Векторы $$ (1,0,0,0),\ (1,1,0,0),\ (1,1,1,1),\ (1,0,1,0) $$ линейно независимы. В том же поле элемент $ (0,0,1,0) $ не порождает нормальный базис.

1)
Можно рассматривать и столбцы — это непринципиально.
2)
cardinalis (лат.) — 1) количественный; 2) главный, основной; 3) кардинал.
linear_space/gf2.txt · Последние изменения: 2023/06/09 23:06 — au