کد خطی کیست؟ توضیح بده.
در تئوری کدگذاری کانال مخابراتی ، کد خطی (به انگلیسی: Linear code)، یک کد تصحیح‌کننده خطاست که هر ترکیب خطی از کلمات کد (به انگلیسی: Codeword) نیز یک کلمه کد است. کدهای خطی، به کدهای بلوکی و کدهای کانولوشنال تقسیم می‌شوند، گرچه کدهای توربو را نیز می‌توان ترکیبی از این دو دانست. کدهای خطی، کدگذاری و کدگشایی کارآمدتری نسبت به دیگر کدها دارند.کدهای خطی برای "تصحیح خطای روبه‌جلو" (به انگلیسی: Forward error correction) در انتقال سمبل‌ها (برای نمونه، بیت‌ها) در یک کانال مخابراتی به‌کار می‌روند تا درصورت خطا در انتقال، برخی از خطاها از سوی گیرنده تصحیح، یا دست‌کم، شناسایی شوند. کلمات کد در یک کد بلوک خطی، بلوک‌هایی از سمبل‌ها هستند که با سمبل‌های بیشتری (نسبت به سمبل‌های اصلی) هنگام ارسال، کدگذاری شده‌اند. یک کد خطی به طول formula_1"،" بلوک‌های formula_1-سمبلی را ارسال می‌کند.برای نمونه، کد همینگ [7، 4، 3]، یک کد باینری بلوکی خطی است که پیام‌های 4-بیتی را با کلمات کد 7-بیتی نشان می‌دهد؛ دو کلمه کد متمایز، حداقل در سه بیت تفاوت دارند. در نتیجه، حداکثر، دو خطا در هر کلمه کد قابل شناسایی است، درحالی‌که یک خطا را می‌توان تصحیح کرد. این کد، formula_3 کلمه کد دارد.تعریف و پارامترها.کد خطی به طول formula_1 و بُعد formula_5"،" یک زیرفضای خطی "formula_6" با بُعد formula_5 از فضای برداری formula_8 است، که formula_9 میدان متناهی با formula_10 مؤلفه است. به چنین کدی، کد "q"- می‌گویند. اگر formula_11 یا formula_12 باشد، کد را به‌ترتیب، کد باینری یا کد سه‌تایی می‌گویند. بردارها در formula_1"،" "کلمات کد" هستند. اندازه یک کد، تعداد کلمات کد، و برابر formula_14 است.وزن یک کلمه کد، تعداد عناصر غیرصفر آن است، و فاصله دو کلمه کد، فاصله همینگ آن‌هاست، یعنی تعداد عناصری که در آن‌ها تفاوت دارند. فاصله formula_1 کد خطی، حداقل وزن کلمات کد غیرصفر آن، یا حداقل فاصله کلمات کد متمایز است. یک کد خطی با طول formula_1 ، بُعد formula_5 و فاصله formula_18 ، کد formula_19 نامیده می‌شود (یا دقیق‌تر، کد formula_20).برای formula_8، "پایۀ" استاندارد تعریف می‌شود، زیرا هر مختصات نشان‌دهنده یک "بیت" است که از راه یک "کانال نویزی" با احتمال خطای انتقال کمی (یک کانال متقارن باینری ) منتقل می‌شود. اگر پایۀ دیگری استفاده شود، این مدل نمی‌تواند استفاده شود و فاصله همینگ، تعداد خطاهای انتقال را آن‌طور که می‌خواهیم، تعیین نمی‌کند.ماتریس‌های مولد و بررسی کد.به عنوان یک زیرفضای خطی از formula_8 ، کد formula_6 (که ممکن است بسیار بزرگ باشد) ممکن است به عنوان گسترۀ مجموعه‌ای از formula_5 کلمه کد نشان داده‌شود (که به عنوان پایه در جبر خطی شناخته می شود). این کدهای پایه، اغلب در ردیف‌های ماتریس formula_25 که به‌عنوان ماتریس مولد کد formula_6 شناخته می‌شود، قرار می‌گیرند. اگر formula_25 شکل ماتریس بلوکی داشته‌باشد، یعنی formula_28، که formula_29 ماتریس واحد formula_30 و formula_31 ماتریسی formula_32 است. در این حالت، formula_25، شکل استاندارد دارد.ماتریس formula_34"،" که یک تابع خطی formula_35 را نشان می‌دهد که هسته آن formula_6 است، ماتریس بررسی formula_6 (به انگلیسی: Check matrix)، یا گاهی ماتریس بررسی برابری (به انگلیسی: Parity check matrix) نامیده می‌شود. به طور معادل، formula_34 ماتریسی است که formula_6، "هستۀ" آن است. اگر formula_6 یک کد با ماتریس مولد formula_25 به شکل استاندارد باشد، formula_28، formula_43 یک ماتریس بررسی برای formula_6 است. کد تولیدشده با formula_34 ، کد دوگان formula_6 نامیده می‌شود. می‌توان نشان داد که formula_25 یک ماتریس formula_48 است، درحالی‌که formula_34 یک ماتریس formula_50 است.خطی‌بودن کد، تضمین می‌کند که دست‌کم فاصله همینگ formula_18 کلمه کد formula_52 و هر یک از کلمات کد دیگر formula_53، مستقل از formula_52 است. این از آن‌جا می‌آید که formula_55 نیز یک کلمه کد از formula_6 (یعنی عنصری از زیرفضای "formula_6") است و این‌که formula_58. این خواص دلالت بر آن دارد که:به عبارت دیگر، برای یافتن حداقل فاصله کلمات کد یک کد خطی، تنها لازم است که به کلمات کد غیرصفر نگاه کرد. کلمه کد غیرصفر با کوچک‌ترین وزن، حداقل فاصله را با کلمه کد صفر دارد و از این رو حداقل فاصله کد را تعیین می‌کند.فاصله formula_18 کد خطی formula_6، با حداقل تعداد ستون‌های وابسته خطی formula_34 نیز برابر است."اثبات:" چون formula_63 ، که معادل است formula_64، که formula_65، ستون formula_66ام formula_34 است. با حذف مواردی که formula_68 ، آنهایی از formula_65 که formula_70، وابسته خطی هستند. از این رو، formula_18 حداقل تعداد ستون های وابسته خطی formula_34 است. از سوی دیگر، با درنظرگرفتن حداقل مجموعه ستون‌های وابسته خطی formula_73، که formula_74 مجموعه شاخص ستون است: formula_75 . حال با درنظرگرفتن بردار formula_76 طوری‌که formula_77، اگر formula_78: formula_79 زیرا formula_80 . بنابراین، formula_81، و حداقل تعداد ستون های وابسته خطی formula_34 است.مثال: کدهای همینگ.به عنوان نخستین کلاس از کدهای خطی تصحیح‌کننده خطا، "کدهای همینگ"، در سیستم های مخابراتی دیجیتال، گسترده استفاده می‌شوند.برای هر عدد صحیح مثبت formula_83، کد همینگ با formula_84 نشان داده‌می‌شود. ازآن‌جاکه formula_85، کد همینگ می‌تواند تنها یک بیت خطا را تصحیح کند.مثال : کد بلوک خطی با ماتریس مولد و ماتریس بررسی برابری زیر، یک کد همینگ formula_86 است.مثال: کد آدامار.کد آدامار (به انگلیسی: Hadamard code)، یک کد خطی formula_89 است که می‌تواند بسیاری از خطاها را تصحیح کند. این کد می‌تواند ستون‌به‌ستون ساخته‌ شود: ستون formula_66ام، بیت های نمایش باینری عدد صحیح formula_66 است، همان‌طور که در مثال زیر نشان داده‌ شده‌است. کد آدامار، دارای حداقل فاصله formula_92 است و بنابراین می‌تواند formula_93 خطا را تصحیح کند.مثال: کد بلوک خطی با ماتریس مولد زیر، یک کد آدامار formula_94 است:formula_95 .کد آدامار، یک مورد خاص از کد رید-مالر (Reed-Muller) است. اگر ستون اول (ستون تمام‌صفر) را از formula_96 خارج کنیم، یک "کد سیمپلکس" formula_97، که "کد دوگان کد" همینگ است، به‌دست می‌آید.الگوریتم نزدیک‌ترین همسایه.پارامتر formula_18، ارتباط نزدیکی با توانایی تصحیح خطای کد دارد. ساختار/الگوریتم زیر، این را نشان می دهد (که الگوریتم رمزگشایی نزدیکترین همسایه نامیده می‌شود):ورودی: یک "بردار دریافت‌شده" formula_99 در formula_8 .خروجی: یک کلمه کد formula_101 در formula_6 که نزدیکترین به formula_99 است، اگر یافت شود.می‌گوییم formula_6، formula_107 خطا را تصحیح می‌کند، اگر حداکثر یک کلمه کد در formula_109 برای هر formula_99 در formula_8 باشد.نماد رایج.کدها، اغلب با formula_6 نشان داده‌می‌شوند و یک کد به‌طول formula_1 و رتبه formula_5 (یعنی formula_5 کلمه کد در پایه کد، و formula_5 ردیف در "ماتریس مولد" آن) به طور کلی با formula_127 شناخته میشود. کدهای بلوکی خطی اغلب به‌صورت formula_19، که formula_18"،" حداقل فاصله همینگ هر دو کلمه کد است، اشاره دارد.formula_19 نباید با formula_131 که نمادی که برای نشان‌دادن یک کد "غیرخطی" به طول formula_1 ، اندازه formula_133 (formula_133 کلمه کد) و حداقل فاصله همینگ formula_18 است، اشتباه شود.قید سینگِلتون (به انگلیسی: Singleton bound)."لِم" (قید سینگِلتُون): برای هر کد formula_19 خطی formula_6، داریم formula_138 .کد formula_6 که پارامترهای آن، formula_140 را برآورده کند، حداکثر فاصله قابل تفکیک یا MDS نامیده می‌شود. چنین کدهایی، اگر یافت شوند، بهترین کدها هستند.کدهای معادل: اگر formula_141 و formula_142 دو کد به طول formula_1، و formula_144 یک جایگشت در گروه متقارن formula_145 که برای آن formula_146 در formula_141 باشد، اگر و فقط اگر، formula_148 در formula_142 باشد، آن‌گاه formula_141 و formula_142، جایگشت-معادل هستند. به‌طور کلی‌تر، اگر ماتریس مونومیال formula_152 formula_153 باشد که formula_141 را ایزومورفیک به formula_142 بفرستد، آن‌گاه formula_141 و formula_142 معادل هستند."لم" : هر کد خطی، جایگشت-معادلِ کدی است که به شکل استاندارد است.قضیه بونیسولی.یک کد، هم‌فاصله است، اگر، و تنها اگر، ثابت formula_18 یافت شود به‌طوری‌که فاصله هر دو کلمه کد متمایز، formula_18 باشد. ۱۹۸۴، آریگو بونیسولی، ساختار کدهای خطی تک-وزن را روی میدان‌های محدود تعیین و ثابت کرد که هر کد خطی هم‌فاصله، دنباله‌ای از کدهای همینگ دوگان است.