کدگذاری شانون

در زمینه‌ی فشرده‌سازی داده، کدگذاری شانون، که به افتخار کشف‌کننده آن، آقای کلود شانون نامگذاری شده‌است، تکنیکی برای فشرده‌سازی بدون اتلاف و ساختن یک کد پیشوندی برمبنای مجموعه‌ای از نمادها و احتمالات آنها (تخمینی ویا اندازه‌گیری شده) می‌باشد. می‌توان گفت این روش غیربهینه می‌باشد، بدین‌جهت که کوتاه‌ترین طول ممکن پیش‌بینی شده کلمات را همانند کدگذاری هافمن به دست نمی‌دهد، و در بهترین شرایط معادل کدگذاری شانون-فانو می‌باشد.

این روش کدگذاری منجر به رشد و توسعه‌ی گرایش فناوری اطلاعات شد و بدون سهم و مشارکت آن در این امر، دنیا از بسیاری از جانشینان آن همچون کدگذاری شانون-فانو، کدگذاری هافمن و کدگذاری حسابی (arithmetic coding) بی‌بهره می‌ماند. بخش عمده‌ای از زندگی روزمره‌ی ما به شکل قابل ملاحظه‌ای متاثر از داده‌ی دیجیتال می‌باشد و این بدون کدگذاری شانون و روند مستدام رشد و تکامل جانشینان آن در روش‌های کدگذاری امکان‌پذیر نمی‌بود.

در کدگذاری شانون، نمادها به ترتیب از پراحتمال‌ترین به کم‌احتمال‌ترین مرتب می‌شوند و با گرفتن اولین  رقم از نمایش دودویی از احتمال تجمعی  دارای کدکلمه‌ای (codeword) می‌شوند. در اینجا  بیانگر تابعی است که  را رو به بالا گرد می‌نماید.https://en.wikipedia.org/wiki/Shannon_coding

 تاریخچه 

یکی از اولین موارد کاربرد گسترده کدگذاری و فشرده‌سازی اطلاعات با ظهور و گسترش عمده کتاب‌های کد تلگراف (Telegraph Code Books) در اوایل قرن ۲۰ میلادی بود. در این زمان هزینه گزافی برای ارسال تلگرام پرداخت می‌کردند، به‌گونه‌ای که در یک تلگرام میان آمریکا و اروپا هزینه هر کلمه حدوداً یک دلار بود (تقریباً ۳۰ دلار با احتساب تورم تا سال ۲۰۱۵ میلادی). این امر منجر به رشد و توسعه کتاب‌های کد تلگراف و استانداردهای موردنظر آنها شد تا با کلماتی اندک منظور فرد ارسال‌کننده تلگرام منتقل شود و برخی از این کتب امروزه در اینترنت یافت می‌شوند، همانند کد معروف ABC Code که از ویرایش چهارم به بعد تراکم داده را به شکل قابل ملاحظه‌ای بالا برده بود.

در همین حین، کلود شانون که از محققان پیشرو در زمینه‌ی کدگذاری بود نظریه‌ی کدگذاری بدون نویز شانون (Shannon’s noiseless coding theorem) و پس از آن نظریه آنتروپی خود (Shannon’s entropy Theorem) را ارائه نمود که علاوه بر کاربرد در این مسئله‌ی آن روز دنیا، پایه مناسبی برای ادامه رشد نظریه اطلاعات شد.http://math.mit.edu/~goemans/18310S15/noiseless-coding.pdf

روش کدگذاری شانون یکی از اولین‌ها در نوع خود بود، که برای اثبات نظریه‌ی کدگذاری بدون نویز شانون (Shannon’s noiseless coding theorem) در مقاله‌ی سال ۱۹۴۸ میلادی وی تحت عنوان "یک تئوری ریاضی برای ارتباطات" به کارگرفته شد، و لذا یک عنصر مهم در عصر اطلاعات می‌باشد.

 یک مثال 
در جدول زیر نمونه‌ای از تولید کد برای نمادهای a1-6 آمده‌است که در آن li بیانگر توان منفی‌ای از ۲ می‌باشد که کوچکتر یا مساوی احتمال کنونی است. ستون پنجم نیز نمایش مجموع به صورت دودویی می‌باشد و آخرین ستون بیت‌کد هر نماد می‌باشد.

aip(ai)liSum from pi to i-1Sum to p(ai) binaryResult (truncated significand)a10.3620.00.000000a20.1830.360.0100010a30.1830.540.1000100a40.1240.720.10111011a50.0940.840.11011101a60.0740.930.11101110

 منابع 

رده:کدگذاری
رده:کلود شانون
رده:فشرده‌سازی داده‌ها
رده:الگوریتم‌های فشرده‌سازی بی‌اتلاف