تاریخچه نظریه کدگذاری

کاوشگرهای فضایی دهه‌هاست که داده‌ها را از دورترین سیاره‌ها به زمین ارسال می‌کنند. این در حالی است که توان فرستنده‌های رادیویی این دستگاه‌ها، تنها چند وات است. حال سوالی که پیش می‌آید این است که چطور این حجم از داده، بدون گرفتار شدن در بهبوهه‌ی نویزها، از میلیون‌ها مایل دورتر به ما می‌رسد؟برای تحقق این عمل، رشته‌های مختلفی به کمک هم می‌آیند: مهندسی برق، کامپیوتر و ریاضیات.نظریه کدگذاری شاخه‌ای از ریاضیات است که مربوط به انتقال داده‌ها از طریق کانال‌های نویزدار و بازیابی پیام است. نظریه کدگذاری درباره آسان کردن خواندن پیام هاست؛ آن را با رمزنگاری که درباره سخت کردن خواندن پیام‌هاست اشتباه نکنید!فرض کنیم پیام ما در قالب اعداد یا بیت‌های باینری هستند یعنی رشته‌هایی از 0 و 1. ما باید این بیت‌ها را در یک کانال منتقل کنیم (مثلا یک خط تلفن) که به‌صورت تصادفی، خطاهایی در آن رخ می‌دهد اما این خطا‌ها یک نرخ قابل حدس دارند. برای جبران این خطاها، باید بیت‌های بیشتری را در پیام اصلی ارسال کنیم.ساده‌ترین راه برای شناسایی خطا در داده‌های باینری، Parity Code (بیت توازن) است. بیت توازن بعد از هر 7 بیت، یک بیت اضافه ارسال می‌کند. اگرچه، این روش فقط می‌تواند خطاها را شناسایی کند و برای تصحیح آن‌ها باید درخواست کنیم تا داده‌ها را دوباره ارسال کنند!یک راه ساده برای تشخیص و تصحیح خطاها، تکرار هر بیت به تعداد مشخصی است. گیرنده نگاه می‌کند که کدام مقدار، 0 یا 1، بیشتر تکرار می‌شود و فرض می‌کند که این بیت مورد نظر است. این روش می‌تواند نرخ خطاهای 1 در هر 2 بیت ارسال شده را پاسخگو باشد اما هزینه برای این کار، افزایش تعداد تکرار است.روزهای ابتدایینکته منفی روش تکرار این است که تعداد بیت‌های ارسالی را تا حدغیرقابل زیادی بالا می‌برد. در سال 1948، Claude Shannon، که در آزمایشگاه‌های Bell فعالیت می‌کرد، نشان داد که می‌توان پیام‌ها را طوری کدگذاری کرد که تعداد بیت‌های اضافی‌ ِ ارسالی، تا حد ممکن پایین باشند. با این کار، او مبحث نظریه کدگذاری را دایر کرد. متاسفانه اثبات او هیچ دستورالعمل صریحی برای این کدهای مطلوب ارائه نکرده است.دو سال بعد بود که Richard Hamming ، که او هم در آزمایشگاه‌های Bell فعالیت می‌کرد، مطالعه کدهای تصحیح‌شونده‌ای را آغاز کرد که نرخ انتقال اطلاعات در این روش، کارآمدتر از روش تکرار بود. در اولین تلاش، یک کد تولید کرد که چهار حرف اول آن داده‌های واقعی بودند و سه حرف بعدی آن برای چک بود (Check Bit) که این سه حرف نه تنها امکان تشخیص بلکه تصحیح را هم فراهم می‌کرد. توجه کنید انجام این کار در روش تکرار، احتیاج به 9 چک بیت داشت.گفته می‌شود Hamming این کد را بعد از تلاش‌های فراوان برای نوشتن یک پیام روی نوار کاغذی با استفاده از کد توازن اختراع کرد. او غر میزد که "اگر می‌تواند خطا را تشخیص دهد، پس چرا نمی‌تواند تصحیح کند!"در حالیکه Shannon و Hamming روی انتقال اطلاعات در آمریکا کار می‌کردند، John Leech کدهای مشابه را در Group Coding در کمبریج اختراع کرد. این تحقیق شامل کار روی مسئله بسته‌بندی گوی‌ها (Sphere Packing Problem) بود و منجر به ایجاد یک شبکه‌بندی 24 بعدی شد. این تحقیق یک عنصر اصلی برای درک و طبقه‌بندی گروه‌های متقارن بود.کاربردهاارزش کدهای قابل تصحیح در انتقال اطلاعات، چه در زمین چه در فضا، به‌سرعت مورد توجه قرار گرفت و کدهای متنوعی تولید شدند که هم به صرفه‌جویی در ارسال و هم به قابلیت تصحیح خطا دست یافتند. بین سال‌های 1969 و 1973، مریخ‌نورد های ناسا از کد Reed-Muller استفاده کردند. این کد می‌توانست 7 خطا را در 32 بیت تصحیح کند. توجه کنید که این 32 بیت شامل 6 بیت داده واقعی و 26 چک بیت بود! بیش از 160000 بیت در هر ثانیه به زمین ارسال می‌شد.یک کاربرد دیگر کدهای قابل تصحیح، با گسترش دیسک‌ها ارائه شد. در CDها، سیگنال‌ها به‌صورت دیجیتالی رمزگذاری شده‌اند. برای محافظت CDها در برابر خراش‌ها و شکستگی‌ها، از دو نوع کد در هم تنیده استفاده شده که می‌توانند تا 4000 خطا را تصحیح کنند. پخش‌کننده‌های صدا می‌توانند حتی خطاهای بیشتری را با تفسیر سیگنال‌ها تصحیح کنند.تحولات مدرندر سال‌های گذشته تلاش‌های زیادی برای گذشتن از محدودیت‌هایی که Shannon در کارهایش پیش‌بینی کرده بود، انجام شده است. انجام این کار، احتیاج به تکنیک‌هایی از زمینه‌های متنوعی دارد از جمله جبر خطی، نظریه میدان‌ها و هندسه جبری. نظریه کدگذاری نه تنها به حل مسائل خارج از ریاضیات کمک کرده است، بلکه شاخه های دیگر ریاضیات را با مسائل جدید و همچنین راه حل های جدید غنی کرده است.منبع