Rešetke i samodualni kodovi
Sažetak
U ovom radu se bavimo linearnim kodovima, s posebnim naglaskom na binarne samodualne linearne kodove. Promotrit ćemo njihova svojstva i primjenu u teoriji rešetki. Navest ćemo poveznicu binarnih linearnih kodova i rešetki, pod nazivom konstrukcija A.Ključne riječi: samodualni kodovi, rešetke, generirajuća matrica, Gramova matrica, cjelobrojne rešetke, samodualne rešetke, konstrukcija A.
2Uvod
Kodovi su osmišljeni kao sustav koji šifrira poruku prije slanja radi sigurnijeg prijenosa, kako bi se omogućila detekcija i ispravljanje pogrešaka uzrokovanih šumom i smetnjama u komunikacijskom kanalu.
Linearni kodovi, uključujući binarne linearne kodove, koriste generirajuće matrice za stvaranje kodnih riječi koje omogućuju učinkovito kodiranje i dekodiranje. Posebno su značajni samodualni kodovi zbog svojih svojstava koja poboljšavaju otpornost na pogreške.
Rešetke su matematičke strukture koje igraju ključnu ulogu u različitim područjima, uključujući teoriju brojeva, geometriju, kriptografiju i teoriju kodiranja. U kontekstu kriptografije, rešetke su se pokazale posebno korisnima za rješavanje problema koji su teški za klasične metode kao što su faktorizacija velikih brojeva ili diskretni logaritmi. Primjena rešetki u kriptografiji evoluirala je od inicijalnog korištenja za probijanje šifri do suvremenih primjena u kvantnoj kriptografiji, koja teži razvoju kriptosustava sigurnih protiv napada kvantnih računala.
Konstrukcija A je metoda koja povezuje teoriju linearnog kodiranja i teoriju rešetki. Ova metoda omogućuje konstrukciju rešetki iz linearnog koda. Svojstva kodova poput samodualnosti se prenose na rešetku, što omogućuje dodatnu otpornost na pogreške i sigurnosne prednosti. Konstrukcija A posebno je važna u kriptografiji i teoriji informacija, gdje omogućuje stvaranje rešetki otpornijih na kvantne napade.
3Linearni kodovi
Definicija 1. Neka je \mathbb{F}_{q} konačno polje s q elemenata, gdje je q potencija prostog broja i neka je n\in\mathbb{N}. Potprostor \mathcal{C} od \mathbb{F}^{n}_{q} dimenzije k nazivamo [n.k] linearnim kodom nad \mathbb{F}_{q}. Elemente koda \mathcal{C} nazivamo riječima koda \mathcal{C}, a broj n duljinom koda \mathcal{C}.
Linearni kodovi nad poljem \mathbb{F}_{2} se nazivaju binarnim kodovima. U radu ćemo se baviti takvim kodovima.
Definicija 2. Neka je \mathcal{C} linearan [n, k] kod. Generirajuća matrica koda \mathcal{C} je matrica reda k\times n \v{c}iji su retci vektori baze prostora \mathcal{C}.
Kažemo da je generirajuća matrica G[n, k] koda u standardnom obliku ako postoji k\times (n-k) matrica C takva da je G = [I_{k} \mid C], gdje je I_{k} jedinična matrica reda k.
3.1Samodualni kodovi
Definicija 3. Neka je \mathcal{C}[n,k] kod nad \mathbb{F}_{q}. Dualni kod koda \mathcal{C} je:
\mathcal{C}^{\perp} = \lbrace \textbf{x}\in \mathbb{F}_{q}^{n} \mid \textbf{x}\cdot \textbf{c} = 0, \,\forall \textbf{c} \in\mathcal{C} \rbrace ,
gdje je \textbf{x}\cdot\textbf{y}=\displaystyle\sum_{i=1}^{n} x_{i}y_{i}, \textbf{x}=(x_{1},\dots,x_{n}),\,\textbf{y}=(y_{1},\dots,y_{n})\in\mathbb{F}_{q}^{n}.Neka je \mathcal{C}[n,k] kod nad \mathbb{F}_{q} s generirajućom matricom u standardnom obliku G=[I_{k} \mid C]. Tada njegov dualni kod \mathcal{C}^{\bot} ima generirajuću matricu
G^{\perp} = [ -C^{\top} \mid I_{n-k} ].
Definicija 5. Linearni kod \mathcal{C} je samoortogonalan ako je \mathcal{C}\subseteq \mathcal{C}^{\bot}.
Kažemo da je linearni kod \mathcal{C} samodualan ako je \mathcal{C} = \mathcal{C}^{\bot}.
Kažemo da je linearni kod \mathcal{C} samodualan ako je \mathcal{C} = \mathcal{C}^{\bot}.
Napomena 6. Neka je \mathcal{C} linearni [n, k] kod s generirajućom matricom G.
| (1) | \mathcal{C} je samoortogonalan ako i samo ako je GG^{\top} = O, gdje je O nulmatrica. |
| (2) | \mathcal{C} je samodualan ako i samo ako je samoortogonalan i k =\frac{n}{2}. |
Primjer 7. Neka je \mathcal{H}_{3} binarni kod zadan generirajućom matricom:
Kod \mathcal{H}_{3} se zove Hammingov [7,4] kod. Ovim kodom podatke od četiri bita kodiramo u sedam bitova, dodajući tri bita provjere parnosti. Kod \mathcal{H}_{3} može detektirati najviše dvije pogreške ukoliko su se dogodile ili ispraviti najviše jednu pogrešku (vidi više u \cite[Poglavlje 3.5]{l:3}). Dodavanjem bita provjere parnosti dobivamo matricu:
Kod e_{8} generiran matricom G_{e_{8}} se zove prošireni [8,4] Hammingov kod. Budući da vrijedi k=\frac{n}{2} i
G_{\mathcal{H}_{3}} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix}.
Kod \mathcal{H}_{3} se zove Hammingov [7,4] kod. Ovim kodom podatke od četiri bita kodiramo u sedam bitova, dodajući tri bita provjere parnosti. Kod \mathcal{H}_{3} može detektirati najviše dvije pogreške ukoliko su se dogodile ili ispraviti najviše jednu pogrešku (vidi više u \cite[Poglavlje 3.5]{l:3}). Dodavanjem bita provjere parnosti dobivamo matricu:
G_{e_{8}} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}.
Kod e_{8} generiran matricom G_{e_{8}} se zove prošireni [8,4] Hammingov kod. Budući da vrijedi k=\frac{n}{2} i
\begin{align*} G_{e_{8}} G_{e_{8}}^{\top}= \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{bmatrix}= \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \end{align*}
iz napomene 6 slijedi da je kod e_{8} samodualan.
4Rešetke
Rešetka je skup točaka određenih cjelobrojnim linearnim kombinacijama podskupa neke baze u n-dimenzionalnom prostoru. Možemo je vizualizirati kao beskonačnu mrežu pravilno raspoređenih točaka.
Definicija 8. Neka je B=\lbrace \textbf{v}_{1},\textbf{v}_{2},\dots,\textbf{v}_{n}\rbrace baza za \mathbb{R}^{n}. Rešetka \Lambda u \mathbb{R}^{n} generirana s B je
Elemente rešetke \Lambda zovemo točkama rešetke \Lambda, dok skup B zovemo bazom rešetke \Lambda. Često se koristi sljedeći matrični zapis baze rešetke \Lambda:
gdje je \textbf{v}_{i}=(v_{i1},v_{i2},\dots ,v_{in}), i=1,\dots,n. Matricu M nazivamo generirajućom matricom rešetke \Lambda. Definirat ćemo rešetke pomoću generirajuće matrice M\in M_{n}(\mathbb{R}) na sljedeći način:
\Lambda=\Lambda(B)= \Bigg\lbrace \sum_{i=1}^{n} z_{i}\textbf{v}_{i}\mid z_{i}\in\mathbb{Z},\, 1\le i\le n\Bigg\rbrace .
Elemente rešetke \Lambda zovemo točkama rešetke \Lambda, dok skup B zovemo bazom rešetke \Lambda. Često se koristi sljedeći matrični zapis baze rešetke \Lambda:
(1)
M=\begin{bmatrix} v_{11} & v_{12} & \dots & v_{1n} \\ v_{21} & v_{22} & \dots & v_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ v_{n1} & v_{n2} & \dots & v_{nn} \end{bmatrix},
\Lambda=\Lambda(M)=\lbrace \textbf{z}M \mid \textbf{z}\in\mathbb{Z}^{n}\rbrace .
Koristit ćemo i sljedeći način označavanja rešetke \Lambda generirane s B=\lbrace \textbf{v}_{1},\textbf{v}_{2},\dots,\textbf{v}_{n}\rbrace:
\Lambda=\Lambda(\textbf{v}_{1},\textbf{v}_{2},\dots,\textbf{v}_{n}).
Definicija 9. Neka je \Lambda rešetka u \mathbb{R}^{n} s generirajućom matricom M\in M_{n}(\mathbb{R}). Gramova matrica rešetke \Lambda je matrica A=MM^{\top}\in M_{n}(\mathbb{R}).
Elementi Gramove matrice A su standardni skalarni produkti u \mathbb{R}^{n} vektora baze rešetke \Lambda.
Definicija 10. Neka je \Lambda rešetka u \mathbb{R}^{n} s bazom B=\lbrace \textbf{v}_{1},\textbf{v}_{2}, \dots, \textbf{v}_{n}\rbrace. Fundamentalna domena rešetke \Lambda je skup
Determinanta rešetke \Lambda je n-dimenzionalni volumen od \mathcal{F}. Označava se sa \det\Lambda.
\mathcal{F}=\mathcal{F}(B) = \left\lbrace t_{1}\textbf{v}_{1} + t_{2}\textbf{v}_{2} + \dots + t_{n}\textbf{v}_{n} \mid 0\leq t_{i}\lt 1,\, 1\le i\le n \right\rbrace .
Determinanta rešetke \Lambda je n-dimenzionalni volumen od \mathcal{F}. Označava se sa \det\Lambda.
Propozicija 11. Neka je \Lambda rešetka u \mathbb{R}^{n} s generirajućom matricom M i fundamentalnom domenom \mathcal{F}. Tada za volumen od \mathcal{F}, u oznaci \text{Vol }\mathcal{F}, vrijedi sljedeća jednakost:
Dokaz propozicije 11 može se naći u
\text{Vol }\mathcal{F} = |\det M|.
(2)
\det\Lambda=\text{Vol }\mathcal{F}=|\det M|.
Definicija 12. Neka je \Lambda rešetka u \mathbb{R}^{n}. Kažemo da je rešetka \Lambda cjelobrojna ako vrijedi
\forall\textbf{x,y}\in\Lambda\quad\textbf{x}\cdot \textbf{y}\in\mathbb{Z},
gdje je \textbf{x}\cdot \textbf{y} standardni skalarni produkt u \mathbb{R}^{n}.Ako Gramova matrica rešetke \Lambda ima cjelobrojne elemente, tada je rešetka \Lambda cjelobrojna.
Primjer 13. Odredimo determinantu, Gramovu matricu i fundamentalnu domenu rešetke
Budući da matrica A_{2} ima cjelobrojne vrijednosti, slijedi da je rešetka \Lambda_{2} cjelobrojna. Na slici1 prikazana je rešetka \Lambda_{2} te njena fundamentalna domena obojena plavom bojom. Ova rešetka naziva se planarnom heksagonalnom rešetkom.
\Lambda_{2}=\Lambda_{2}(M_{2})\text{, gdje je } M_{2}=\begin{bmatrix} \sqrt{2} & 0 \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{6}}{2} \end{bmatrix}.
\det\Lambda_{2}= \begin{vmatrix} \sqrt{2} & 0 \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{6}}{2} \end{vmatrix}=\sqrt{3},\ A_{2}=M_{2}M_{2}^{\top}= \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}.
Budući da matrica A_{2} ima cjelobrojne vrijednosti, slijedi da je rešetka \Lambda_{2} cjelobrojna. Na slici
4.1Samodualne rešetke
Definicija 14. Neka je \Lambda rešetka u \mathbb{R}^{n}. Njena dualna rešetka \Lambda^{*} je
\Lambda^{*}=\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{x}\cdot \textbf{y}\in\mathbb{Z},\, \forall \textbf{x}\in\Lambda\rbrace .
Definicija 15. Kažemo da je cjelobrojna rešetka \Lambda samodualna (unimodularna) ako vrijedi \Lambda=\Lambda^{*}.
Teorem 16. [3 , Teorem 10.6.3] Neka je\Lambda rešetka u \mathbb{R}^{n} s bazom B=\lbrace \textbf{v}_{1},\textbf{v}_{2}\dots,\textbf{v}_{n}\rbrace te s pripadnom generirajućom matricom M i Gramovom matricom A. Tada vrijedi:
| (i) | \Lambda^{*}=\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{v}_{i}\cdot \textbf{y}\in\mathbb{Z},\,\forall 1\leq i \leq n\rbrace = \lbrace \textbf{y}\in\mathbb{R}^{n} \mid \textbf{y}M^{\top}\in \mathbb{Z}^{n}\rbrace. |
| (ii) | Generirajuća matrica od \Lambda^{*} je (M^{-1})^{\top}. |
| (iii) | Gramova matrica od \Lambda^{*} je A^{-1}. |
| (iv) | \det\Lambda^{*} = 1/\det\Lambda. |
| (v) | \Lambda je cjelobrojna ako i samo ako je \Lambda\subseteq\Lambda^{*}. |
| (vi) |
Ako je \Lambda cjelobrojna, tada vrijedi
\Lambda\subseteq\Lambda^{*}\subseteq\frac{1}{\det \Lambda}\Lambda = (\det\Lambda^{*})\Lambda.
|
| (vii) | Ako je \Lambda cjelobrojna, tada je \Lambda samodualna ako i samo ako je \det\Lambda=1. |
Dokaz. Neka je \Lambda=\Lambda(\textbf{v}_{1},\textbf{v}_{2}\dots,\textbf{v}_{n}) rešetka u \mathbb{R}^{n} s generirajućom matricom M i Gramovom matricom A.
| (i) |
Uočimo da jednakost
\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{x}\cdot \textbf{y}\in\mathbb{Z},\,\forall \textbf{x}\in\Lambda\rbrace = \lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{v}_{i}\cdot\textbf{y}\in\mathbb{Z},\,\forall 1\leq i \leq n\rbrace
vrijedi zbog linearnosti skalarnog produkta u \mathbb{R}^{n}.Nadalje, dokažimo drugu jednakost:
\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{v}_{i}\cdot \textbf{y}\in\mathbb{Z},\,\forall1\leq i \leq n\rbrace = \lbrace \textbf{y}\in\mathbb{R}^{n} \mid \textbf{y}M^{\top}\in \mathbb{Z}^{n}\rbrace .
Neka je \textbf{y}\in\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{v}_{i}\cdot \textbf{y}\in\mathbb{Z},\,\forall1\leq i \leq n\rbrace. Za \textbf{y}=(y_{1},\dots, y_{n}) i \textbf{v}_{i}=(v_{i1},\dots, v_{in}), i=1,\dots,n, možemo pisati:
\textbf{y}M^{\top}=\begin{bmatrix} \textbf{v}_{1}\cdot\textbf{y} & \textbf{v}_{2}\cdot\textbf{y} & \dots & \textbf{v}_{n}\cdot\textbf{y} \end{bmatrix}.
Budući da vrijedi \textbf{v}_{i}\cdot \textbf{y}\in\mathbb{Z},\forall1\leq i \leq n, slijedi da je \textbf{y}M^{\top} \in \mathbb{Z}^{n}.Neka je sada \textbf{y} \in\mathbb{R}^{n} takav da je \textbf{y}M^{\top} \in \mathbb{Z}^{n}. To znači da su svi elementi vektora \textbf{y}M^{\top} cijeli brojevi, pa je \textbf{y}\in\lbrace \textbf{y}\in\mathbb{R}^{n}\mid \textbf{v}_{i}\cdot \textbf{y}\in\mathbb{Z},\forall1\leq i \leq n\rbrace. |
| (ii) |
Neka su \textbf{w}_1,\dots, \textbf{w}_{n} retci matrice (M^{-1})^{\top}. Tada je \lbrace \textbf{w}_{1},\dots, \textbf{w}_{n}\rbrace baza za \mathbb{R}^{n}. Budući da je (M^{-1})^{\top} M^{\top} = (MM^{-1})^{\top} = I_{n}, vrijedi
(3)
\textbf{w}_{i} \cdot \textbf{v}_{j} = \begin{cases} 1 & \text{ ako je } i = j, \\ 0 & \text{ ako je } i \neq j. \end{cases}
\displaystyle\textbf{w} = a_{1}\textbf{w}_{1} + \ldots + a_{n}\textbf{w}_{n}, budući da je \lbrace \textbf{w}_{1},\dots, \textbf{w}_{n}\rbrace baza za \mathbb{R}^{n}. Kako je \textbf{w}\in \Lambda^{*}, \textbf{w}\cdot \textbf{v}_{j} \in \mathbb{Z}, za j\in\lbrace 1,\dots,n\rbrace. No, \textbf{w} \cdot \textbf{v}_{j} = a_{j}, za 1 \leq j \leq n, prema (
\Lambda^{*}=\lbrace \textbf{z}\,(M^{-1})^{\top}\mid\textbf{z}\in\mathbb{Z}^{n}\rbrace .
|
| (iii) |
Odredimo sada Gramovu matricu rešetke \Lambda^{*}. Prema svojstvu (ii), vrijedi
(M^{-1})^{\top} M^{-1} = (MM^{\top})^{-1} = A^{-1},
iz čega slijedi da je A^{-1} Gramova matrica rešetke \Lambda^{*}. |
| (iv) |
Odredimo sada determinantu rešetke \Lambda^{*}. Iz (ii) slijedi
\det \Lambda^{*} = |\det (M^{-1})^{\top}|=|\det (M^{-1})|=\frac{1}{|\det M|} = \frac{1}{\det \Lambda}.
|
| (v) |
Dokažimo tvrdnju: ako je rešetka \Lambda cjelobrojna, tada vrijedi \Lambda\subseteq\Lambda^{*}. Neka je \Lambda je cjelobrojna rešetka. Tada vrijedi
\forall\textbf{x}\in\Lambda\Rightarrow\textbf{x}\in\Lambda^{*},
kako se dualna rešetka sastoji od vektora \textbf{y} takvih da \textbf{x}\cdot\textbf{y}\in\mathbb{Z}, \forall\textbf{x}\in\Lambda.Dokažimo sada: ako vrijedi \Lambda\subseteq\Lambda^{*}, tada je rešetka \Lambda cjelobrojna. Neka je \Lambda\subseteq\Lambda^{*}. Tada vrijedi:
\forall\textbf{x,y}\in\Lambda\subseteq\Lambda^{*}\Rightarrow\textbf{x}\cdot \textbf{y}\in\mathbb{Z},\, \forall\textbf{y}\in\Lambda,
pa je rešetka \Lambda cjelobrojna. |
| (vi) |
Neka je rešetka \Lambda cjelobrojna. Prema svojstvu (v) vrijedi \Lambda\subseteq\Lambda^{*}. Uzmimo proizvoljan \textbf{y}\in\Lambda^{*}. Tada je \textbf{y} M^{\top} \in \mathbb{Z}^{n} prema (i), stoga postoji \textbf{z}\in\mathbb{Z}^{n} za koji vrijedi
\textbf{y} = \textbf{z}\,(M^{\top})^{-1} = \textbf{z}\,(M^{\top})^{-1}M^{-1}M = \textbf{z}\,(MM^{\top})^{-1}M = \textbf{z}\,A^{-1}M.
Matricu A^{-1} možemo zapisati na sljedeći način:
A^{-1} = (\det A)^{-1}\text{adj}(A),
gdje je \text{adj}(A)={\left[(-1)^{i+j}M_{ij}\right]}^{\top}. Kako je \Lambda cjelobrojna rešetka, matrica A je cjelobrojna, pa su minore M_{ij}\in \mathbb{Z}, za 1\leq i,j \leq n.Nadalje,
\textbf{y}= \textbf{z}\,(\det A)^{-1} \text{adj}(A)M = \textbf{z}'\,(\det A)^{-1}M,
gdje je \textbf{z}' = \textbf{z}\,\text{adj}(A) \in \mathbb{Z}^{n}, budući da \text{adj}(A) ima cjelobrojne vrijednosti. Dakle, \textbf{y}\in (\det \Lambda)^{-1}\Lambda pa vrijedi svojstvo (vi). |
| (vii) |
Neka je \Lambda cjelobrojna rešetka. Dokažimo najprije tvrdnju: ako je \Lambda samodualna, tada vrijedi \det\Lambda=1. Prema svojstvu (iv), vrijedi
\det \Lambda = \det \Lambda^{*} = \frac{1}{\det \Lambda},
iz čega slijedi \det \Lambda =1, jer je \det\Lambda\gt 0.Neka sada vrijedi \det \Lambda =1. Prema svojstvu (vi) vrijedi
\Lambda \subseteq \Lambda^{*} \subseteq \frac{1}{\det \Lambda}\Lambda= \Lambda,
pa je \Lambda^{*}=\Lambda. |
\square
Primjer 17. Odredimo dualnu rešetku \Lambda_{2}^{*} planarne heksagonalne rešetke \Lambda_{2}=\Lambda_{2}(M_{2}) te njenu determinantu i fundamentalnu domenu.
Prema teoremu 16 (ii), generirajuća matrica dualne rešetke \Lambda_{2}^{*} je2 su točke dualne rešetke \Lambda_{2}^{*} i njena fundamentalna domena obojene crvenom bojom.
Prema teoremu 16 (ii), generirajuća matrica dualne rešetke \Lambda_{2}^{*} je
(M_{2}^{-1})^{\top}=\begin{bmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{6}}{6} \\ 0 & \frac{\sqrt{6}}{3} \end{bmatrix}.
Stoga vrijedi:
\Lambda^{*}_{2}=\lbrace \textbf{z}\,(M_{2}^{-1})^{\top}\mid \textbf{z}\in\mathbb{Z}^{2} \rbrace =\left\lbrace \left(\frac{\sqrt{2}}{2}z_{1}, -\frac{\sqrt{6}}{6}z_{1}+\frac{\sqrt{6}}{3}z_{2}\right) \mid z_{1}, z_{2}\in \mathbb{Z}\right\rbrace .
Nadalje, po teoremu 16 (iv) slijedi
\det\Lambda_{2}^{*}=\frac{1}{\det\Lambda_{2}}=\frac{\sqrt{3}}{3}.
Podskupovnost \Lambda_{2}\subseteq\Lambda_{2}^{*}
slijedi iz teorema 16 (v) i \v{c}injenice da je rešetka \Lambda_{2} cjelobrojna. Nadalje, prema teoremu 16 (vii) i iz \v{c}injenice da je \det\Lambda_{2}=\sqrt{3}, slijedi da \Lambda_{2} nije samodualna rešetka. Na slici 
5Konstrukcija A
Sada navodimo konstrukciju rešetki iz binarnih kodova, poznatu pod nazivom Konstrukcija A.
Neka je \mathcal{C} binarni kod duljine n. Tada je rešetka određena kodom \mathcal{C} jednaka
\Lambda(\mathcal{C}) = \lbrace \textbf{x} \in \mathbb{R}^{n} \mid \sqrt{2}\textbf{x} \,(\text{mod }{2}) \in \mathcal{C}\rbrace .
Neka je \mathcal{C} binarni [n,k] kod s generirajućom matricom u standardnom obliku G=[I_{k}\mid C]. Tada rešetka \Lambda(\mathcal{C}), konstruirana konstrukcijom A iz koda \mathcal{C}, ima generirajuću matricu:
M=\frac{1}{\sqrt{2}} \begin{bmatrix} I_{k} & C \\ O & 2\,I_{n-k} \end{bmatrix},
gdje je O nulmatrica, a I_{n} jedinična matrica reda n. Gramova matrica rešetke \Lambda(\mathcal{C}) jednaka je:
A=\frac{1}{2} \begin{bmatrix} I_{k} + CC^{\top} & 2C \\ 2C^{\top} & 4I_{n-k} \end{bmatrix}.
Teorem 18. [3 , Teorem 10.6.4] Neka je \mathcal{C} binarni [n, k] kod. Tada vrijedi:
| (i) | \det\Lambda(\mathcal{C}) = 2^{\frac{n-2k}{2}}. |
| (ii) | \Lambda(\mathcal{C}^{\perp}) = \Lambda(\mathcal{C})^{*}. |
| (iii) | Rešetka \Lambda(\mathcal{C}) je cjelobrojna ako i samo ako je kod \mathcal{C} samoortogonalan. |
| (iv) | Rešetka \Lambda(\mathcal{C}) je samodualna ako i samo ako je kod \mathcal{C} samodualan. |
Dokaz. Neka je \mathcal{C} binarni [n,k] kod s generirajućom matricom u standardnom obliku G = [I_{k} \mid C] i \Lambda(\mathcal{C}) rešetka konstruirana iz koda \mathcal{C} konstrukcijom A s generirajućom matricom M.
| (i) |
Vrijedi:
\det M=2^{-\frac{n}{2}}\det I_{k}\cdot \det (2I_{n-k}) =2^{\frac{n-2k}{2}}.
Tada, prema ( |
| (ii) |
Budući da je G^{\perp} = [ C^{\top} \mid I_{n-k} ] generirajuća matrica od \mathcal{C}^{\perp}, \Lambda(\mathcal{C}^{\perp}) ima generirajuću matricu
M^{\perp} = \frac{1}{\sqrt{2}} \begin{bmatrix} C^{\top} & I_{n-k} \\ 2I_{k} & O \end{bmatrix}.
Skalarni produkt retka iz G s retkom iz G^{\perp} je 0. Slijedi da je realni skalarni produkt retka iz M s retkom iz M^{\perp} cijeli broj. Tada je M^{\perp}M^{\top} matrica s cjelobrojnim vrijednostima, te vrijedi \Lambda(\mathcal{C}^{\perp}) \subseteq \Lambda(\mathcal{C})^{\ast}.Neka je sada \textbf{y} \in \Lambda(\mathcal{C})^{*}. Tada je \textbf{y}M^{\top} \in \mathbb{Z}^{n}, prema teoremu 16 (i). Dakle, postoji \textbf{z} \in \mathbb{Z}^{n} takav da je
\textbf{y} = \textbf{z}(M^{\top})^{-1} = \textbf{z}(M^{\top})^{-1} (M^{\perp})^{-1} M^{\perp} = \textbf{z}(M^{\perp} M^{\top})^{-1} M^{\perp}.
Kako je M^{\perp} M^{\top} matrica s cjelobrojnim vrijednostima, vrijedi:
\det(M^{\perp} M^{\top}) = \det(M^{\perp}) \det(M^{\top}) = \pm 2^{\frac{2k-n}{2}} \cdot (2^{\frac{n-2k}{2}}) = \pm 1
pa i matrica
(M^{\perp} M^{\top})^{-1} = \frac{1}{\det(M^{\perp} M^{\top})} \, \operatorname{adj}(M^{\perp} M^{\top})
ima cjelobrojne vrijednosti. Dakle, \textbf{y} = \textbf{z'}M^{\perp} za neki \textbf{z}' \in \mathbb{Z}^{n}. Stoga je \textbf{y} \in \Lambda(\mathcal{C}^{\perp}). |
| (iii) | Ova tvrdnja slijedi iz činjenice da je realni skalarni produkt dvaju redaka iz M cijeli broj ako i samo ako je binarni skalarni produkt redaka iz G jednak 0. |
| (iv) |
Neka je rešetka \Lambda(\mathcal{C}) samodualna. Tada je rešetka \Lambda(\mathcal{C}) cjelobrojna iz čega slijedi da je kod \mathcal{C} samoortogonalan, prema (iii). Zatim, prema teoremu 16 (vii), vrijedi \det\Lambda(\mathcal{C}) = 1, \v{s}to implicira k=\frac{n}{2}. Prema napomeni 6, kod \mathcal{C} je samodualan. Neka je kod \mathcal{C} samodualan. Tada, prema (ii), vrijedi \Lambda(\mathcal{C}) = \Lambda(\mathcal{C}^{\perp}) = \Lambda(\mathcal{C})^{*}, iz čega slijedi da je \Lambda(\mathcal{C}) samodualna rešetka. |
\square
Primjer 19. Odredimo rešetku \Lambda(e_{8}) konstrukcijom A iz proširenog [8,4] Hammingovog koda e_{8}. Generirajuća i Gramova matrica rešetke \Lambda(e_{8}) su jednake:
Prema teoremu 18 (iv), slijedi da je rešetka \Lambda(e_{8}) samodualna, kako je kod e_{8} samodualan.
M=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{bmatrix}, \quad A=\begin{bmatrix} 2 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 2 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 2 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 2 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 2 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 2 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 2 \end{bmatrix}.
Nadalje, \det (\Lambda(e_{8}))= 2^{\frac{8-2\cdot 4}{2}}=1.Prema teoremu 18 (iv), slijedi da je rešetka \Lambda(e_{8}) samodualna, kako je kod e_{8} samodualan.
6Zaključak
Binarni linearni kodovi, uz pomoć generirajućih matrica, omogućuju učinkovitu izgradnju kodnih riječi, dok samodualni kodovi pružaju dodatna svojstva koja su korisna u različitim kontekstima, kao na primjer ispravljanju grešaka, kriptografiji te u teoriji rešetki i kvantnoj teoriji.
Rešetke proširuju primjene teorije kodiranja u područjima poput kriptografije i teorije brojeva. Imaju široku primjenu kod bežične komunikacije u mobilnim komunikacijskim sustavima poput 4G i 5G mreža, u satelitskoj komunikaciji, kod digitalne televizije i radija, te pohrane podataka na memorijskim uređajima.
Konstrukcija A predstavlja ključnu metodu za povezivanje linearnih kodova s rešetkama, omogućujući prijenos korisnih svojstava između ovih dvaju područja.
Napomena: Članak je nastao iz diplomskog rada studentice Margarete Crnčić, pod mentorstvom doc. dr. sc. Sare Ban Martinović, na diplomskom studiju Diskretna matematika i primjene Fakulteta za matematiku Sveučilišta u Rijeci.
Bibliografija
