موضوع مقاله: کد خطی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کد خطی | مقدمه: کدهای خطی، به کدهای بلوکی و کدهای کانولوشنال تقسیم می‌شوند، گرچه کدهای توربو را نیز می‌توان ترکیبی از این دو دانست. | ## بخش 1: کد خطی | کلمات کد در یک کد بلوک خطی، بلوک‌هایی از سمبل‌ها هستند که با سمبل‌های بیشتری (نسبت به سمبل‌های اصلی) هنگام ارسال، کدگذاری شده‌اند. برای نمونه، کد همینگ [7، 4، 3]، یک کد باینری بلوکی خطی است که پیام‌های 4-بیتی را با کلمات کد 7-بیتی نشان می‌دهد؛ دو کلمه کد متمایز، حداقل در سه بیت تفاوت دارند. در نتیجه، حداکثر، دو خطا در هر کلمه کد قابل شناسایی است، درحالی‌که یک خطا را می‌توان تصحیح کرد. تعریف و پارامترها کد خطی به طول و بُعد ، یک زیرفضای خطی با بُعد از فضای برداری است، که میدان متناهی با مؤلفه است. وزن یک کلمه کد، تعداد عناصر غیرصفر آن است، و فاصله دو کلمه کد، فاصله همینگ آن‌هاست، یعنی تعداد عناصری که در آن‌ها تفاوت دارند. برای ، پایۀ استاندارد تعریف می‌شود، زیرا هر مختصات نشان‌دهنده یک بیت است که از راه یک کانال نویزی با احتمال خطای انتقال کمی (یک کانال متقارن باینری ) منتقل می‌شود. اگر پایۀ دیگری استفاده شود، این مدل نمی‌تواند استفاده شود و فاصله همینگ، تعداد خطاهای انتقال را آن‌طور که می‌خواهیم، تعیین نمی‌کند. ماتریس‌های مولد و بررسی کد به عنوان یک زیرفضای خطی از ، کد (که ممکن است بسیار بزرگ باشد) ممکن است به عنوان گسترۀ مجموعه‌ای از کلمه کد نشان داده‌شود (که به عنوان پایه در جبر خطی شناخته می شود). این کدهای پایه، اغلب در ردیف‌های ماتریس که به‌عنوان ماتریس مولد کد شناخته می‌شود، قرار می‌گیرند. | ## بخش 2: کد خطی | خطی‌بودن کد، تضمین می‌کند که دست‌کم فاصله همینگ کلمه کد و هر یک از کلمات کد دیگر ، مستقل از است. این از آن‌جا می‌آید که نیز یک کلمه کد از (یعنی عنصری از زیرفضای ) است و این‌که . این خواص دلالت بر آن دارد که: به عبارت دیگر، برای یافتن حداقل فاصله کلمات کد یک کد خطی، تنها لازم است که به کلمات کد غیرصفر نگاه کرد. کلمه کد غیرصفر با کوچک‌ترین وزن، حداقل فاصله را با کلمه کد صفر دارد و از این رو حداقل فاصله کد را تعیین می‌کند. از سوی دیگر، با درنظرگرفتن حداقل مجموعه ستون‌های وابسته خطی ، که مجموعه شاخص ستون است: . مثال: کدهای همینگ به عنوان نخستین کلاس از کدهای خطی تصحیح‌کننده خطا، کدهای همینگ، در سیستم های مخابراتی دیجیتال، گسترده استفاده می‌شوند. این کد می‌تواند ستون‌به‌ستون ساخته‌ شود: ستون ام، بیت های نمایش باینری عدد صحیح است، همان‌طور که در مثال زیر نشان داده‌ شده‌است. اگر ستون اول (ستون تمام‌صفر) را از خارج کنیم، یک کد سیمپلکس ، که کد دوگان کد همینگ است، به‌دست می‌آید. الگوریتم نزدیک‌ترین همسایه پارامتر ، ارتباط نزدیکی با توانایی تصحیح خطای کد دارد. | ## بخش 3: کد خطی | ساختار/الگوریتم زیر، این را نشان می دهد (که الگوریتم رمزگشایی نزدیکترین همسایه نامیده می‌شود): ورودی: یک بردار دریافت‌شده در . تعداد نقاط درون توپی به شعاع (همینگ) اطراف بردار دریافت‌شده را، که با نشان داده می‌شود، بشمار. نماد رایج کدها، اغلب با نشان داده‌می‌شوند و یک کد به‌طول و رتبه (یعنی کلمه کد در پایه کد، و ردیف در ماتریس مولد آن) به طور کلی با شناخته میشود. کدهای بلوکی خطی اغلب به‌صورت ، که ، حداقل فاصله همینگ هر دو کلمه کد است، اشاره دارد. نباید با که نمادی که برای نشان‌دادن یک کد غیرخطی به طول ، اندازه ( کلمه کد) و حداقل فاصله همینگ است، اشتباه شود. کد که پارامترهای آن، را برآورده کند، حداکثر فاصله قابل تفکیک یا MDS نامیده می‌شود. کدهای معادل: اگر و دو کد به طول ، و یک جایگشت در گروه متقارن که برای آن در باشد، اگر و فقط اگر، در باشد، آن‌گاه و ، جایگشت-معادل هستند. به‌طور کلی‌تر، اگر ماتریس مونومیال باشد که را ایزومورفیک به بفرستد، آن‌گاه و معادل هستند. قضیه بونیسولی یک کد، هم‌فاصله است، اگر، و تنها اگر، ثابت یافت شود به‌طوری‌که فاصله هر دو کلمه کد متمایز، باشد. | ## جمع‌بندی | ۱۹۸۴، آریگو بونیسولی، ساختار کدهای خطی تک-وزن را روی میدان‌های محدود تعیین و ثابت کرد که هر کد خطی هم‌فاصله، دنباله‌ای از کدهای همینگ دوگان است.