کد خطی

در تئوری کدگذاری کانال مخابراتی ، کد خطی (به انگلیسی: Linear code)، یک کد تصحیح‌کننده خطاست که هر ترکیب خطی از کلمات کد (به انگلیسی: Codeword) نیز یک کلمه کد است. کدهای خطی، به کدهای بلوکی و کدهای کانولوشنال تقسیم می‌شوند، گرچه کدهای توربو را نیز می‌توان ترکیبی از این دو دانست. کدهای خطی، کدگذاری و کدگشایی کارآمدتری نسبت به دیگر کدها دارند.

کدهای خطی برای تصحیح خطای روبه‌جلو (به انگلیسی: Forward error correction) در انتقال سمبول‌ها (برای نمونه، بیت‌ها) در یک کانال مخابراتی به‌کار می‌روند تا درصورت خطا در انتقال، برخی از خطاها از سوی گیرنده تصحیح، یا دست‌کم، شناسایی شوند. کلمات کد در یک کد بلوک خطی، بلوک‌هایی از سمبول‌ها هستند که با سمبول‌های بیشتری (نسبت به سمبول‌های اصلی) هنگام ارسال، کدگذاری شده‌اند. یک کد خطی به طول $n$، بلوک‌های $n$-سمبولی را ارسال می‌کند.

برای نمونه، کد همینگ [7، 4، 3]، یک کد باینری بلوکی خطی است که پیام‌های 4-بیتی را با کلمات کد 7-بیتی نشان می‌دهد؛ دو کلمه کد متمایز، حداقل در سه بیت تفاوت دارند. در نتیجه، حداکثر، دو خطا در هر کلمه کد قابل شناسایی است، درحالی‌که یک خطا را می‌توان تصحیح کرد. این کد، $2^{4}=16$ کلمه کد دارد.

تعریف و پارامترها

کد خطی به طول $n$ و بُعد $k$، یک زیرفضای خطی $C$ با بُعد $k$ از فضای برداری $\mathbb {F} _{q}^{n}$ است، که $\mathbb {F} _{q}$ میدان متناهی با $q$ مؤلفه است. به چنین کدی، کد q-ary می‌گویند. اگر $q=2$ یا $q=3$ باشد، کد را به‌ترتیب، کد باینری یا کد سه‌تایی می‌گویند. بردارها در $n$، کلمات کد هستند. اندازه یک کد، تعداد کلمات کد، و برابر $q^{k}$ است.

وزن یک کلمه کد، تعداد عناصر غیرصفر آن است، و فاصله دو کلمه کد، فاصله همینگ آن‌هاست، یعنی تعداد عناصری که در آن‌ها تفاوت دارند. فاصله $n$ کد خطی، حداقل وزن کلمات کد غیرصفر آن، یا حداقل فاصله کلمات کد متمایز است. یک کد خطی با طول $n$ ، بُعد $k$ و فاصله $d$ ، کد $[n,k,d]$ نامیده می‌شود (یا دقیق‌تر، کد $[n,k,d]_{q}$).

برای $\mathbb {F} _{q}^{n}$، پایۀ استاندارد تعریف می‌شود، زیرا هر مختصات نشان‌دهنده یک بیت است که از راه یک کانال نویزی با احتمال خطای انتقال کمی (یک کانال متقارن باینری ) منتقل می‌شود. اگر پایۀ دیگری استفاده شود، این مدل نمی‌تواند استفاده شود و فاصله همینگ، تعداد خطاهای انتقال را آن‌طور که می‌خواهیم، تعیین نمی‌کند.

ماتریس‌های مولد و بررسی کد

به عنوان یک زیرفضای خطی از $\mathbb {F} _{q}^{n}$ ، کد $C$ (که ممکن است بسیار بزرگ باشد) ممکن است به عنوان گسترۀ مجموعه‌ای از $k$ کلمه کد نشان داده‌شود (که به عنوان پایه در جبر خطی شناخته می شود). این کدهای پایه، اغلب در ردیف‌های ماتریس ${\boldsymbol {G}}$ که به‌عنوان ماتریس مولد کد $C$ شناخته می‌شود، قرار می‌گیرند. اگر ${\boldsymbol {G}}$ شکل ماتریس بلوکی داشته‌باشد، یعنی ${\boldsymbol {G}}=[I_{k}|P]$، که $I_{k}$ ماتریس واحد $k\times k$ و ${\boldsymbol {P}}$ ماتریسی $k\times (n-k)$ است. در این حالت، ${\boldsymbol {G}}$، شکل استاندارد دارد.

ماتریس ${\boldsymbol {H}}$، که یک تابع خطی $\phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}$ را نشان می‌دهد که هسته آن $C$ است، ماتریس بررسی $C$ (به انگلیسی: Check matrix)، یا گاهی ماتریس بررسی برابری (به انگلیسی: Parity check matrix) نامیده می‌شود. به طور معادل، ${\boldsymbol {H}}$ ماتریسی است که $C$، هستۀ آن است. اگر $C$ یک کد با ماتریس مولد ${\boldsymbol {G}}$ به شکل استاندارد باشد، ${\boldsymbol {G}}=[I_{k}|P]$، ${\boldsymbol {H}}=[-P^{T}|I_{n-k}]$ یک ماتریس بررسی برای $C$ است. کد تولیدشده با ${\boldsymbol {H}}$ ، کد دوگان $C$ نامیده می‌شود. می‌توان نشان داد که ${\boldsymbol {G}}$ یک ماتریس $k\times n$ است، درحالی‌که ${\boldsymbol {H}}$ یک ماتریس $(n-k)\times n$ است.

خطی‌بودن کد، تضمین می‌کند که دست‌کم فاصله همینگ $d$ کلمه کد ${\boldsymbol {c}}_{0}$ و هر یک از کلمات کد دیگر ${\boldsymbol {c}}\neq {\boldsymbol {c}}_{0}$، مستقل از ${\boldsymbol {c}}_{0}$ است. این از آن‌جا می‌آید که ${\boldsymbol {c}}_{0}-{\boldsymbol {c}}$ نیز یک کلمه کد از $C$ (یعنی عنصری از زیرفضای $C$) است و این‌که ${\boldsymbol {c}}-{\boldsymbol {c}}_{0}=d({\boldsymbol {c}},{\boldsymbol {c}}_{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.$

به عبارت دیگر، برای یافتن حداقل فاصله کلمات کد یک کد خطی، تنها لازم است که به کلمات کد غیرصفر نگاه کرد. کلمه کد غیرصفر با کوچک‌ترین وزن، حداقل فاصله را با کلمه کد صفر دارد و از این رو حداقل فاصله کد را تعیین می‌کند.

فاصله $d$ کد خطی $C$، با حداقل تعداد ستون‌های وابسته خطی ${\boldsymbol {H}}$ نیز برابر است.

اثبات: چون ${\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}$ ، که معادل است $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}$، که ${\boldsymbol {H_{i}}}$، ستون $i$ام ${\boldsymbol {H}}$ است. با حذف مواردی که $c_{i}=0$ ، آنهایی از ${\boldsymbol {H_{i}}}$ که $c_{i}\neq 0$، وابسته خطی هستند. از این رو، $d$ حداقل تعداد ستون های وابسته خطی ${\boldsymbol {H}}$ است. از سوی دیگر، با درنظرگرفتن حداقل مجموعه ستون‌های وابسته خطی $\{{\boldsymbol {H_{j}}}|j\in S\}$، که $S$ مجموعه شاخص ستون است: $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}$ . حال با درنظرگرفتن بردار ${\boldsymbol {c'}}$ طوری‌که $c_{j}'=0$، اگر $j\notin S$: ${\boldsymbol {c'}}\in C$ زیرا ${\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}$ . بنابراین، $d\leq wt({\boldsymbol {c'}})$، و حداقل تعداد ستون های وابسته خطی ${\boldsymbol {H}}$ است.

مثال: کدهای همینگ

به عنوان نخستین کلاس از کدهای خطی تصحیح‌کننده خطا، کدهای همینگ، در سیستم های مخابراتی دیجیتال، گسترده استفاده می‌شوند.

برای هر عدد صحیح مثبت $r\geq 2$، کد همینگ با $[2^{r}-1,2^{r}-r-1,3]_{2}$ نشان داده‌می‌شود. ازآن‌جاکه $d=3$، کد همینگ می‌تواند تنها یک بیت خطا را تصحیح کند.

مثال : کد بلوک خطی با ماتریس مولد و ماتریس بررسی برابری زیر، یک کد همینگ $[7,4,3]_{2}$ است.

${\boldsymbol {G}}={\begin{pmatrix}1\ 0\ 0\ 0\ 1\ 1\ 0\\0\ 1\ 0\ 0\ 0\ 1\ 1\\0\ 0\ 1\ 0\ 1\ 1\ 1\\0\ 0\ 0\ 1\ 1\ 0\ 1\end{pmatrix}},$ ${\boldsymbol {H}}={\begin{pmatrix}1\ 0\ 1\ 1\ 1\ 0\ 0\\1\ 1\ 1\ 0\ 0\ 1\ 0\\0\ 1\ 1\ 1\ 0\ 0\ 1\end{pmatrix}}$

مثال: کد آدامار

کد آدامار (به انگلیسی: Hadamard code)، یک کد خطی $[2^{r},r,2^{r-1}]_{2}$ است که می‌تواند بسیاری از خطاها را تصحیح کند. این کد می‌تواند ستون‌به‌ستون ساخته‌ شود: ستون $i$ام، بیت های نمایش باینری عدد صحیح $i$ است، همان‌طور که در مثال زیر نشان داده‌ شده‌است. کد آدامار، دارای حداقل فاصله $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}}$ .

کد آدامار، یک مورد خاص از کد رید-مالر (Reed-Muller) است. اگر ستون اول (ستون تمام‌صفر) را از ${\boldsymbol {G}}_{Had}$ خارج کنیم، یک کد سیمپلکس $[7,3,4]_{2}$، که کد دوگان کد همینگ است، به‌دست می‌آید.

الگوریتم نزدیک‌ترین همسایه

پارامتر $d$، ارتباط نزدیکی با توانایی تصحیح خطای کد دارد. ساختار/الگوریتم زیر، این را نشان می دهد (که الگوریتم رمزگشایی نزدیکترین همسایه نامیده می‌شود):

ورودی: یک بردار دریافت‌شده $v$ در $\mathbb {F} _{q}^{n}$ .

خروجی: یک کلمه کد $w$ در $C$ که نزدیکترین به $v$ است، اگر یافت شود.

• شروع با $t=0$ ، دو مرحله زیر را تکرار کن.
• هر کلمه کد را یک نقطه در فضای $n$-بُعدی $\mathbb {F} _{q}^{n}$ در نظر بگیر. تعداد نقاط درون توپی به شعاع (همینگ) $t$ اطراف بردار دریافت‌شده $v$ را، که با $B_{t}(v)$ نشان داده می‌شود، بشمار.
  • برای هر $w$ در $B_{t}(v)$ ، بررسی کن آیا $w$ در $C$ است. اگر چنین بود، $w$ را به عنوان جواب الگوریتم برگردان.
• $t$ را یکی زیاد کن. اگر $t>(d-1)/2$، دیگر ادامه نده؛ شمارش کافی‌ست، و هیچ جوابی پیدا نشده‌است.

می‌گوییم $C$، $t$ خطا را تصحیح می‌کند، اگر حداکثر یک کلمه کد در $B_{t}(v)$ برای هر $v$ در $\mathbb {F} _{q}^{n}$ باشد.

نماد رایج

کدها، اغلب با $C$ نشان داده‌می‌شوند و یک کد به‌طول $n$ و رتبه $k$ (یعنی $k$ کلمه کد در پایه کد، و $k$ ردیف در ماتریس مولد آن) به طور کلی با $[n,k]$ شناخته میشود. کدهای بلوکی خطی اغلب به‌صورت $[n,k,d]$، که $d$، حداقل فاصله همینگ هر دو کلمه کد است، اشاره دارد.

$[n,k,d]$ نباید با $[n,M,d]$ که نمادی که برای نشان‌دادن یک کد غیرخطی به طول $n$ ، اندازه $M$ ($M$ کلمه کد) و حداقل فاصله همینگ $d$ است، اشتباه شود.

قید سینگِلتون (به انگلیسی: Singleton bound)

لِم (قید سینگِلتُون): برای هر کد $[n,k,d]$ خطی $C$، داریم $k+d\leq n+1$ .

کد $C$ که پارامترهای آن، $k+d=n+1$ را برآورده کند، حداکثر فاصله قابل تفکیک یا MDS نامیده می‌شود. چنین کدهایی، اگر یافت شوند، بهترین کدها هستند.

کدهای معادل: اگر $C_{1}$ و $C_{2}$ دو کد به طول $n$، و $p$ یک جایگشت در گروه متقارن $S_{n}$ که برای آن $(c_{1},\dots ,c_{n})$ در $C_{1}$ باشد، اگر و فقط اگر، $(c_{p(1)},\dots ,c_{p(n)})$ در $C_{2}$ باشد، آن‌گاه $C_{1}$ و $C_{2}$، جایگشت-معادل هستند. به‌طور کلی‌تر، اگر ماتریس مونومیال $n\times n$ $M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$ باشد که $C_{1}$ را ایزومورفیک به $C_{2}$ بفرستد، آن‌گاه $C_{1}$ و $C_{2}$ معادل هستند.

لم : هر کد خطی، جایگشت-معادلِ کدی است که به شکل استاندارد است.

قضیه بونیسولی

یک کد، هم‌فاصله است، اگر، و تنها اگر، ثابت $d$ یافت شود به‌طوری‌که فاصله هر دو کلمه کد متمایز، $d$ باشد. ۱۹۸۴، آریگو بونیسولی، ساختار کدهای خطی تک-وزن را روی میدان‌های محدود تعیین و ثابت کرد که هر کد خطی هم‌فاصله، دنباله‌ای از کدهای همینگ دوگان است.