نظریه کدگذاری
نظریه کُدینگ یا کُدگذاری (با رمزنگاری یا رمزگذاری اشتباه نشود) به بررسی روش‌های کدگذاری اطلاعات می‌پردازد و یکی از موضوعات مهم در بخش‌های مختلف علوم (مثل نظریه اطلاعات، مهندسی برق، ریاضیات و علوم رایانه، انتقال داده) است؛ به این ترتیب که می‌توان با استفاده از آن روش‌های مطمئن برای انتقال داده‌ها طراحی کرد به طوری که تکرارهای بی‌مورد، حذف و خطاها کاهش یابد.
در علوم مهندسی مانند مهندسی برق و رایانه، در ترجمهٔ واژهٔ «Code» به فارسی باید دقت و احتیاط کرد، و از ترجمهٔ آن به واژه «رمز» خودداری و به همان «کُد» بسنده کرد. چرا که واژهٔ «رمز» در این علوم، معنیِ کاملاً متفاوتی با آنچه که منظورمان از به کاربردن «Code» است، دارد. در غیر این صورت، این کار باعث ابهام در مفاهیمی مانند Coding، Encoding، و Decoding که در مهندسی برق بسیار رایجند می‌شود. مثلاً، دو واژهٔ «کدگذاری» و «رمزگذاری» به دو مفهوم کاملاً متفاوت و نامرتبط اشاره میکنند؛ کدگذاری اطلاعات (Data Encoding) با رمزگذاری اطلاعات (Data Encryption)، یکی نیست و هدف آن‌ها دو چیز کاملاً متفاوت است. و یا در علوم رایانه، کدنویسی (Coding)، همان برنامه‌نویسی (Programming) است، و هیچ ربطی به رمزنویسی (Cryptography) ندارد.
نظریه کدگذاری (Coding Theory) در سال ۱۹۴۸ توسط ریچارد هَمینگ پایه‌ریزی شد. وی پی برد هنگامی که رایانه از یک عمل رایج نسخه‌برداری می‌کند و با عمل دیگری شروع به کار می‌کند، هرگز نمی‌تواند به حالت اولیه بازگردد. نظریه کدگذاری مثال خوبی از کاربرد ریاضی محض در حل مسائل عملی است. اگر چه برخی از کدهای ساده دارای ساختاری هستند که نیاز زیادی به ریاضیات ندارند، با این حال ویژگی کدها از کشفیات ریاضیات است.
دسته‌بندی
سه دسته کدگذاری وجود دارد:
- کدگذاری منبع (فشرده‌سازی داده‌ها)
- کدگذاری کانال (تشخیص و تصحیح خطای انتقال داده ها)
- کدگذاری توأم منبع و کانال
در مورد اول، کدگذاری منبع، برای انتقال مؤثرتر داده‌ها، آن‌ها را فشرده کند. مثال عملی روزمره آن در اینترنت، وقتی از فُرمَت فایل zip برای انتقال فایل‌های مختلف استفاده می‌کنیم، است. چرا که حجم فایل مورد انتقال را کم کرده و ترافیک شبکه را کاهش می‌دهد. مورد دوم، کدگذاری کانال، بیت‌هایی را به داده‌های مورد انتقال اضافه می‌کند تا آن‌ها را در برابر اختلالات مسیر انتقال (نویز، تداخل) سالم به مقصد برساند. کاربر عادی ممکن است از کاربردهای معمول این نوع کدگذاری بی‌خبر باشد. برای نمونه یک CD معمولی از روش کدگذاری Reed-Solomon برای تصحیح خطای ناشی از خراش و غبار استفاده می‌کند. در این مثال مسیر انتقال داده خود CD خواهد بود. گوشی‌های همراه نیز از نوعی کدگذاری برای تصحیح خطای ناشی از محو شدگی (Fading) سیگنال و نویز، بهره می‌برد.
کدگذاری منبع (Source Coding)
به‌طور ساده هدف این کار این است که داده‌های منبع را گرفته و آن را فشرده کند.
اصل کدگذاری منبع
اِنتروپی یا آنتروپیِ (Entropy) منبع اطلاعات، بیانگر میزان اطلاعات آن منبع است. اساساً روش‌های کدگذاری منبع تکرارهای بی‌مورد را کم میکنند تا با بیت‌های کمتر، اطلاعات بیشتری را منتقل کنند. فشرده‌سازی داده‌ها، متوسط طول پیام‌های ارسالی را بر اساس یک مدل احتمالاتی به نام entropy encoding کاهش دهد. برنامه‌های فشرده ساز از تکنیک‌های متعددی استفاده میکنند تا به حد آنتروپی منبع یعنی (C(x) ≥ H(x برسند؛ که در آن (H(x انتروپی منبع و (C(x انتروپی فایل پس از پردازش است. در موارد خاص هیچ روش کدگذاری برای منبع، بهتر از خود کد منبع نیست.
کدگذاری کانال (Channel Coding)
هدف این کدگذاری یافتن کدهایی است که سریع تر و بی خطاتر منتقل می‌شوند، شامل تعداد زیادی کدواژه (Keyword) هستند و می‌توانند خطاها را تصحیح کنند یا اینکه حداقل تعداد زیادی از خطاها را تشخیص دهند. ویژگی‌های هر کد بستگی به این دارد که در انتقال آن کد احتمال وقوع چه خطاهایی وجود دارد، برای نمونه در CDهای معمولی خطاهای رایج، خراش‌ها و گرد و غبار هستند. پس داده‌ها روی سطح دیسک توزیع می‌شوند. یک مثال ساده، کدگذاریِ تکرار (Repetition Code) است. در این روش هر بیت را سه بار می‌فرستیم. در مقصد، دریافت‌کننده بیت‌ها را بیت به بیت چک می‌کند و آن بیت را که در سه بار تکرار، فراوانی بیشتری دارد به عنوان بیت صحیح برمی‌گزیند. البته در عمل، روش‌های پیچیده تری برای کدگذاری کانال استفاده می‌شود.
کدگذاری جبری کانال (Algebraic Coding Theory)
نظریهٔ کدگذاری جبری زیر مجموعه‌ای از نظریهٔ کدگذاری است که در آن ویژگی کدها با عبارات جبری بیان می‌شود. نظریهٔ کدگذاری جبری اساساً به دو دسته تقسیم می‌شود:
- کدهایی خطی بلوکی (Linear Block Codes)
- کدهای کانوُلوشِنال (Convolutional)
این نظریه سه ویژگی زیر از کدها را بررسی می‌کند:
- طول کدواژه ها
- تعداد کدواژه ها
- حداقل فاصلهٔ میان دو کدواژه، مثلاً با استفاده از روش فاصلهٔ همینگ (Hamming Distance)
افزایش حداقل فاصله میان دو کدواژه، قابلیت تشخیص و تصحیح خطا را افزایش می‌دهد.
کاربردهای دیگری از کدها
غیر از آنچه که در بالا به آن اشاره شد، طراحی کد برای همزمان سازی (Synchronization)، از دیگر کاربردهای کدهاست. یک کد می‌تواند طوری طراحی شود که به راحتی جابجایی فاز (موج) را تشخیص دهد و تصحیح کند، و اینکه از یک مسیر چند سیگنال را بفرستد.
دیگر کاربرد کدها که در برخی از گوشی‌های همراه استفاده می‌شود، دسترسی چندگانه تقسیم کُدی (Code Division Multiple Access, CDMA) است.
مرتبط
منابع
- Vera Pless (1982)، Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc. , ISBN 0-471-08684-3.
- Elwyn R. Berlekamp (1984)، Algebraic Coding Theory, Aegean Park Press (revised edition), ISBN 0-89412-063-8، ISBN 978-0-89412-063-3.
- Randy Yates, A Coding Theory Tutorial.