نمایش مبدأ برای کد خطی

در [[نظریه کدگذاری|تئوری کدگذاری]] [[کانال مخابراتی]] ، '''کد خطی''' (به [[انگلیسی]]: Linear code)، یک کد تصحیح‌کننده خطاست که هر [[ترکیب خطی]] از کلمات کد (به [[انگلیسی]]: Codeword) نیز یک کلمه کد است. کدهای خطی، به کدهای بلوکی و [[کد کانولوشنال|کدهای کانولوشنال]] تقسیم می‌شوند، گرچه [[کد توربو|کدهای توربو]] را نیز می‌توان ترکیبی از این دو دانست.  کدهای خطی، کدگذاری و کدگشایی کارآمدتری نسبت به دیگر کدها دارند.<ref>{{cite book|title=Channel Codes: Classical and Modern|url=https://archive.org/details/channelcodesclas00ryan|url-access=limited|author=William E. Ryan and Shu Lin|page=[https://archive.org/details/channelcodesclas00ryan/page/n21 4]|year=2009|publisher=Cambridge University Press|isbn=978-0-521-84868-8}}</ref>

کدهای خطی برای ''تصحیح خطای روبه‌جلو'' (به [[انگلیسی]]: Forward error correction) در انتقال سمبل‌ها (برای نمونه، [[بیت (رایانه)|بیت‌ها]]) در یک [[کانال مخابراتی]] به‌کار می‌روند تا درصورت خطا در انتقال، برخی از خطاها از سوی گیرنده تصحیح، یا دست‌کم، شناسایی شوند. کلمات کد در یک کد بلوک خطی، بلوک‌هایی از سمبل‌ها هستند که با سمبل‌های بیشتری (نسبت به سمبل‌های اصلی) هنگام ارسال، کدگذاری شده‌اند.  یک کد خطی به طول <math>n</math>''،'' بلوک‌های <math>n</math>-سمبلی را ارسال می‌کند.<ref name="DrMacKayECC">{{cite book|last=MacKay|first=David, J.C.|authorlink=David J.C. MacKay|title=Information Theory, Inference, and Learning Algorithms|year=2003|pages=9|publisher=[[Cambridge University Press]]|isbn=9780521642989|url=http://www.inference.phy.cam.ac.uk/itprnn/book.pdf|quote="In a ''linear'' block code, the extra <math>N - K</math> bits are linear functions of the original <math>K</math> bits; these extra bits are called ''parity-check bits''"|bibcode=2003itil.book.....M}}</ref>

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

== تعریف و پارامترها ==
'''کد خطی''' به طول <math>n</math> و بُعد <math>k</math>''،'' یک [[زیرفضای خطی]] ''<math>C</math>'' با [[بعد (فضای برداری)|بُعد]] <math>k</math> از [[فضای برداری]] <math>\mathbb{F}_q^n</math> است، که <math>\mathbb{F}_q</math> [[میدان متناهی]] با <math>q</math> مؤلفه است. به چنین کدی، کد ''q''- می‌گویند. اگر <math>q=2</math> یا <math>q=3</math> باشد، کد را به‌ترتیب، '''کد باینری''' یا '''کد سه‌تایی''' می‌گویند. بردارها در <math>n</math>''،'' ''کلمات کد'' هستند. '''اندازه''' یک کد، تعداد کلمات کد، و برابر <math>q^k</math> است.

'''وزن''' یک کلمه کد، تعداد عناصر غیرصفر آن است، و '''فاصله''' دو کلمه کد، [[فاصله همینگ]] آن‌هاست، یعنی تعداد عناصری که در آن‌ها تفاوت دارند. فاصله <math>n</math> کد خطی، حداقل وزن کلمات کد غیرصفر آن، یا حداقل فاصله کلمات کد متمایز است. یک کد خطی با طول <math>n</math> ، بُعد <math>k</math> و فاصله <math>d</math> ، کد <math>[n,k,d]</math> نامیده می‌شود (یا دقیق‌تر، کد <math>[n,k,d]_q</math>).

برای <math>\mathbb{F}_q^n</math>، ''پایۀ'' استاندارد تعریف می‌شود، زیرا هر مختصات نشان‌دهنده یک ''بیت'' است که از راه یک ''کانال نویزی'' با احتمال خطای انتقال کمی (یک [[کانال دودویی متقارن|کانال متقارن باینری]] ) منتقل می‌شود. اگر پایۀ دیگری استفاده شود، این مدل نمی‌تواند استفاده شود و فاصله همینگ، تعداد خطاهای انتقال را آن‌طور که می‌خواهیم، تعیین نمی‌کند.

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

ماتریس <ref>{{Cite journal|date=2024-07-20|title=ماتریس|url=https://fa.wikipedia.org/w/index.php?title=%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B3&oldid=39911769|journal=ویکی‌پدیا، دانشنامهٔ آزاد|language=fa}}</ref><math>\boldsymbol{H}</math>''،'' که یک تابع خطی<ref>{{Cite journal|date=2021-03-03|title=تابع خطی|url=https://fa.wikipedia.org/w/index.php?title=%D8%AA%D8%A7%D8%A8%D8%B9_%D8%AE%D8%B7%DB%8C&oldid=31342838|journal=ویکی‌پدیا، دانشنامهٔ آزاد|language=fa}}</ref> <math>\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}</math> را نشان می‌دهد که [[هسته (جبر خطی)|هسته]] آن <math>C</math> است، '''[[ماتریس بررسی همزادی|ماتریس بررسی]]''' <math>C</math> (به [[انگلیسی]]: Check matrix)، یا گاهی '''ماتریس بررسی برابری''' (به [[انگلیسی]]: Parity check matrix) نامیده می‌شود. به طور معادل، <math>\boldsymbol{H}</math> ماتریسی است که <math>C</math>، ''هستۀ'' آن است. اگر <math>C</math> یک کد با ماتریس مولد <math>\boldsymbol{G}</math> به شکل استاندارد باشد، <math>\boldsymbol{G} = [I_k | P]</math>، <math>\boldsymbol{H} = [-P^{T} | I_{n-k} ]</math> یک ماتریس بررسی برای <math>C</math> است. کد تولیدشده با <math>\boldsymbol{H}</math> '''، کد دوگان''' <math>C</math> نامیده می‌شود. می‌توان نشان داد که <math>\boldsymbol{G}</math> یک ماتریس <math>k \times n</math> است، درحالی‌که <math>\boldsymbol{H}</math> یک ماتریس <math>(n-k) \times n</math> است.

خطی‌بودن کد، تضمین می‌کند که دست‌کم [[فاصله همینگ]] <math>d</math> کلمه کد <math>\boldsymbol{c}_0</math> و هر یک از کلمات کد دیگر <math>\boldsymbol{c} \neq \boldsymbol{c}_0</math>، مستقل از <math>\boldsymbol{c}_0</math> است. این از آن‌جا می‌آید که <math>\boldsymbol{c}_0 - \boldsymbol{c}</math>  نیز یک کلمه کد از <math>C</math> (یعنی [[عنصر (ریاضیات)|عنصری]] از زیرفضای ''<math>C</math>'') است و این‌که <math>\boldsymbol{c} - \boldsymbol{c}_0 = d(\boldsymbol{c} , \boldsymbol{c}_0)</math>. این خواص دلالت بر آن دارد که:

: <math>\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.</math>

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

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

''اثبات:'' چون <math>\boldsymbol{H} \cdot \boldsymbol{c}^T = \boldsymbol{0}</math> ، که معادل است <math>\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \boldsymbol{0}</math>، که <math>\boldsymbol{H_i}</math>، ستون <math>i</math>ام <math>\boldsymbol{H}</math> است. با حذف مواردی که <math>c_i=0</math> ، آنهایی از <math>\boldsymbol{H_i}</math> که <math>c_i \neq 0</math>، وابسته خطی هستند. از این رو، <math>d</math> حداقل تعداد ستون های وابسته خطی <math>\boldsymbol{H}</math> است. از سوی دیگر، با درنظرگرفتن حداقل مجموعه ستون‌های وابسته خطی <math>\{ \boldsymbol{H_j} | j \in S \}</math>، که <math>S</math> مجموعه شاخص ستون است: <math>\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}</math> . حال  با درنظرگرفتن بردار <math>\boldsymbol{c'}</math> طوری‌که <math>c_j'=0</math>، اگر <math>j \notin S</math>: <math>\boldsymbol{c'} \in C</math> زیرا <math>\boldsymbol{H} \cdot \boldsymbol{c'}^T = \boldsymbol{0}</math> . بنابراین، <math>d \le wt(\boldsymbol{c'}) </math>، و حداقل تعداد ستون های وابسته خطی <math>\boldsymbol{H}</math> است.

== مثال: کدهای همینگ ==
به عنوان نخستین کلاس از کدهای خطی تصحیح‌کننده خطا، [[کد همینگ|''کدهای همینگ'']]، در سیستم های مخابراتی دیجیتال، گسترده استفاده می‌شوند.

برای هر عدد صحیح مثبت <math>r \ge 2 </math>، کد همینگ با <math> [2^r-1, 2^r-r-1,3]_2</math> نشان داده‌می‌شود. ازآن‌جاکه <math>d=3</math>، کد همینگ می‌تواند تنها یک بیت خطا را تصحیح کند.

'''مثال :''' کد بلوک خطی با ماتریس مولد و ماتریس بررسی برابری زیر، یک کد همینگ<ref>{{Cite journal|date=2023-02-23|title=کد همینگ|url=https://fa.wikipedia.org/w/index.php?title=%DA%A9%D8%AF_%D9%87%D9%85%DB%8C%D9%86%DA%AF&oldid=36620533|journal=ویکی‌پدیا، دانشنامهٔ آزاد|language=fa}}</ref> <math> [7,4,3]_2</math> است.

: <math>\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}  ,</math> <math>\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}</math>

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

'''مثال:''' کد بلوک خطی با ماتریس مولد زیر، یک کد آدامار <math> [8,3,4]_2</math> است:

<math>\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}</math> .

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

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

ورودی: یک ''بردار دریافت‌شده'' <math>v</math> در <math>\mathbb{F}_q^n</math> .

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

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

می‌گوییم <math>C</math>، <math>t</math> خطا را تصحیح می‌کند، اگر حداکثر یک کلمه کد در <math>B_t(v)</math> برای هر <math>v</math> در <math>\mathbb{F}_q^n</math> باشد.

== نماد رایج ==
[[کد|کدها]]، اغلب با <math>C</math> نشان داده‌می‌شوند و یک کد به‌طول <math>n</math> و [[بعد (فضای برداری)|رتبه]] <math>k</math> (یعنی <math>k</math> کلمه کد در پایه کد، و <math>k</math> ردیف در ''ماتریس مولد'' آن) به طور کلی با <math>[n,k]</math> شناخته میشود. کدهای بلوکی خطی اغلب به‌صورت <math>[n,k,d]</math>، که <math>d</math>''،'' حداقل فاصله همینگ هر دو کلمه کد است، اشاره دارد.

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

== قید سینگِلتون (به [[انگلیسی]]: Singleton bound) ==
''لِم'' (قید سینگِلتُون): برای هر کد <math>[n,k,d]</math> خطی <math>C</math>، داریم <math>k+d \leq n+1</math> .

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

'''کدهای معادل''': اگر <math>C_1</math> و <math>C_2</math> دو کد به طول <math>n</math>، و <math>p</math> یک جایگشت در [[گروه متقارن]] <math>S_n</math> که برای آن <math>(c_1, \dots, c_n)</math> در <math>C_1</math> باشد، اگر و فقط اگر، <math>(c_{p(1)}, \dots, c_{p(n)})</math> در <math>C_2</math> باشد، آن‌گاه <math>C_1</math> و <math>C_2</math>، '''جایگشت-معادل''' هستند. به‌طور کلی‌تر، اگر ماتریس مونومیال <math>n\times n</math>   <math>M\colon \mathbb{F}_q^n \to \mathbb{F}_q^n</math> باشد که <math>C_1</math> را [[ایزومورفیسم|ایزومورفیک]] به <math>C_2</math> بفرستد، آن‌گاه <math>C_1</math> و <math>C_2</math> '''معادل''' هستند.

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

== قضیه بونیسولی ==
یک کد، '''هم‌فاصله''' است، اگر، و تنها اگر، ثابت <math>d</math> یافت شود به‌طوری‌که فاصله هر دو کلمه کد متمایز، <math>d</math> باشد. ۱۹۸۴، آریگو بونیسولی، ساختار کدهای خطی تک-وزن را روی میدان‌های محدود تعیین و ثابت کرد که هر کد خطی  هم‌فاصله، دنباله‌ای از [[کد همینگ|کدهای همینگ]] دوگان است.<ref>{{Cite journal|last=Bonisoli, A.|year=1984|title=Every equidistant linear code is a sequence of dual Hamming codes|journal=Ars Combinatoria|volume=18|pages=181–186}}</ref>

== منابع ==
{{پانویس}}

[[رده:میدان‌های متناهی]]
[[رده:نظریه کدگذاری]]