Шугаман код

Шугаман код (Англи: linear code) Кодчилолын онолд шугаман код гэдэг нь алдаа засдаг код error correcting code бөгөөд ямар ч кодчлогдсон үгсийн шугаман нэгдэл linear combination нь бас кодчлогдсон үг болдог. Уламжлал ёсоор шугаман кодыг блок код block code, эргэсэн код convolutional code болон эдгээрийн эрлийз болох турбо код turbo code гэж хуваана.

Шугаман кодуудыг урьдчилан алдаа засхад forward error correction мөн харилцаа холбооны сувагаар communication channe тэмдэгт дамжуулах аргад хэрэглэнэ. Тиймээс холбоонд алдаа гарвал блок мессежийг хүлээн авагч зарим алдааг илрүүлж засах боломжтой. Шугаман блок кодын кодлогдсон үгс нь тэмдэгтүүдийн блокууд бөгөөд тэдгээр тэмдэгтийг шифрлэхийн encode тулд анх явуулах гэж байсан хэмжээнээс олон тэмдэгт ашигладаг. nурттай шугаман код n ширхэг тэмдэгт агуулсан блокуудийг дамжуулдаг.

Жишээ нь: [7,4,3] Хэмингийн код Hamming code нь 7 бит кодлогдсон үгсийг ашиглан 4 бит мессежийг илэрхийлдэг шугаман хоёртын код (Загвар:Leng-en) юм. Хоорондоо ялгаатай кодлогдсон үгс нь дор хаяж гурван битийн ялгаатай байдаг. Үүний үр дүнд кодлогдсон үг бүрийн хувьд хоёр алдаа илрүүлж, нэг алдаа засах боломжтой.

Тодорхойлолт болон үзүүлэлтүүд

N урттай k зэрэгтэй шугаман код нь вектор зай (vector space) $\mathbb {F} _{q}^{n}$ к хэмжээст шугаман дэд зай subspace C юм. Энд $\mathbb {F} _{q}^{n}$ нь q элементтэй төгсгөлөг талбар. Хэрвээ q = 2 байвал хоёртын, q = 3 байвал гурвалсан код гэнэ. C-н векторуудыг кодлогдсон үгс гэнэ. Кодын хэмжээ нь кодлогдсон үгсийн тоо бөгөөд q^k -той тэнцүү.

Кодлогдсон үгсийн жин гэдэг нь түүний тэгтэй тэнцүү биш элементүүдийн тоо, хоёр кодлогдсон үгийн хоорондох зай нь тэдгээрийн хоорондох Хэмингийн зай Hamming distance, өөрөөр хэлбэл тэдгээрийн ялгаатай эпементийн тоо юм. Шугаман кодын хоорондох зай d нь тэгтэй тэнцүү биш кодлогдсон үгсийн хамгийн бага жин, өөр хоорондоо ялгаатай хоёр кодлогдсон үгийн хоорондох хамгийн бага зай юм.N урттай k хэмжээст d зайтай шугаман кодыг [n,k,d] код гэнэ.

Шинж чанарууд

$\mathbb {F} _{q}^{n}$ -н шугаман дэд зайн linear subspace хувьд нийт код Cнь кодлогдсон үгсийн хамгийн бага олонлогийн завсараар span дүрслэгддэг. Эдгээр үндсэн кодлогдсон үгс нь үүсгэх матриц generating matrix G-н мөрнүүдтэй тэнцдэг.Gнь $G=(I_{k}|A)$ гэсэн блок матриц хэлбэртэй байвал G-г стандарт хэлбэр байна гэнэ.Энд $I_{k}$ нь $k\times k$ identity matrix, A нь ямар нэг $k\times (n-k)$ матрицыг заана.

Матриц H нь шугаман функц $\phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}$ -г илэрхийлнэ. Түүний цөм kernel C-г C-н шалгах матриц check matrix (заримдаа parity check matrix) гэнэ. Өөрөөр хэлбэл H бол хоосон орон зай null space нь C байх матриц юм. Хэрвээ C стандарт хэлбэрт байгаа үүсгэх матриц generating matrix G–г агуулсан G = (I_k | A) байвал H = (−A^t | I_n − k) нь C–д шалгах матриц check matrix болж өгнө.H-н үүсгэсэн кодыг C-н хосолсон код dual code гэж нэрлэнэ.

c₀ болон c ≠ c₀ байх өөр кодлогдсон үг хоёрын хоорондох хамгийн бага Хэмингийн зай Hamming distance d c₀-оос хамааралгүй байна гэдгийг шугаман хамаарал батална. Энэ нь C-н кодлогдсон үгсийн хоорондын ялгаа c − c₀ нь бас кодлогдсон үг болдог гэсэн шинж чанар, мөн d(c, co)=d(c-co, 0) гэсэн шинж чанараас дагаж мөрдөгдөнө. Эдгээр шинж чанараас:

\min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,c\neq 0}d(c,0)=d.

Өөрөөр хэлбэл шугаман кодын кодлогдсон үгсийн хоорондох хамгийн бага зайг олохын тулд зөвхөн тэгтэй тэнцүү биш кодлогдсон үгсийг харах хэрэгтэй. Тэгтэй тэнцүү биш хамгийн бага жинтэй кодлогдсон үгсийн хувьд хамгийн бага зайтай байдаг кодлогдсон үг нь тэг кодлогдсон үг юм. Эндээс кодын хамгийн бага зайг тодорхойлно.

Жишээ: Хадамард код

Хадамард код гэдэг нь $[2^{r},r,2^{r-1}]_{2}$ гэсэн шугаман код бөгөөд олон алдааг засах чадвартай юм. Хадамард кодыг багана баганааар нь жагсаадаг : $i^{th}$ арга нь бол Т багана нь i бүхэл тооны хоёрын тooлын нэг хэсэг юм. Хадамар код нь $2^{r-1}$ зайд хамгийн багадаа оршдог ч $2^{r-2}-1$ алдааг засаж чаддаг.

Жишээ нь: дараах үүсгэгчийн матрицын хувьд шугаман хаалтын код $[8,3,4]_{2}$ хадамард код нь:

${\boldsymbol {G}}_{Had}={\begin{pmatrix}0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}}$ .

Хадамард код нь Мьюлерийн кодын тусгай код бөгөөд хэрэв бид эхний баганыг( бүх багана 0 тэнцүү байх) ${\boldsymbol {G}}_{Had}$ гэдгээс авбал давхар код Хамминг код болох $[7,3,4]_{2}$ энгийн кодыг олох болно.

Хамгийн ойрын алгоритм

d параметр нь алдааг засах чадвартай кодтой холбоотой байдаг. Дараах бүтэц буюу алгоритмийг доор үзүүллэ. (Хамгийн ойрхон алгоритмийг тайлбарлах гэж тодорхойлдог.):
Оролт: $\mathbb {F} _{q}^{n}$ дэх хүлээн авсан вектор v.
Гаралт: v-тэй хамгийн ойр байх C-дэх w кодчлол.

v-г хүлээн авсан t радиусын тойргийн элементүүдйиг илэрхийлэгдэхгүй нь B_t -д хамаарагддаг.
- B_t(v)-дэх w бүрийн хувьд С-дэх w-ийг шалгах ёстой.
Илэрхийлэлгүй үед ямар нэгэн шийдвэр олдохгүй.

Тэмдэглэл: Бууралт нь t > (d − 1)/2 багагүй байдаг. Энэ С шугамыг бид $\mathbb {F} _{q}^{n}$ –дэх v бүрийн B_t(v) кодтой үед t алдааг засдаг.

Нийтлэг тэмдэглээ

Гол сэдэв нь: Хаалтын код
Ерөнхийдөө кодууд нь С үсгээр илэрхийлэгддэг, k нь хэмжигдэхүүн болон n нь уртын код нь ерөнхийдөө (n, k) кодод хамааралтай байдаг. Шугаман хаалтын код нь [n, k, d] кодоор илэрхийлэгддэг нь аливаа 2 кодын хооронд орших хамминг зайнд хамааргдах d болно. Тэмдгэлэгээ: [n, k, d] тэмдгэлгээ нь n уртын шугаман бус кодыг илэрхийлэхэд ашигладаг тэмдгэлгээ, M хэмжээ болон d хамгийн бага хамминг зай нь шугман бус кодыг илэрхийлэхэд ашигладаг тэмдгэлгээ (n, M, d) тэмдэглэгээтэй андуурч болохгүй.

Дан хязгаар

Лемма (Дан хязгаар): Бүх шугаман [n, k, d] код С нь $k+d\leq n+1$ -ийг хангадаг.
С кодны параметрүүд нь k+d=n+1 хангаж байвал хамгийн их зайг тусгарлагч гэж нэрлэдэг. Ийм кодууд байвал хамгийн оновчтой шийдүүд гарч ирдэг.
Хэрэв C₁ , C₂ нь n уртын код гэвэл C₂ дахь эсвэл C₁-д зориулсан S_n (c₁,...,c_n) үед мөн (c_p(1),...,c_p(n)) төсөөтэй ижил бүлгүүд дэх p өөрчлөлт гарч ирвэл бид C₁ , C₂ -ийг өөрчлөлтийн эквивалент гэж болно. Хэрэв C₂ руу C₁- ийг илгээдэг $n\times n$ нэг гишүүнт матриц нь $M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$ байвал C₁ болон С-г эквивалент гэж болно.
Лемма: Аливаа шугаман код нь стандарт хэлбэртэй байдаг кодны өөрчлөлтийн эквивалент юм.