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

تصویر کلود شانون (۱۰ اردیبهشت ۱۲۹۵ خورشیدی - ۶ اسفند ۱۳۷۹)، ریاضی‌دان، مهندس الکترونیک و رمزنگار معروف آمریکاییِ اهل میشیگان است که به عنوان پدر نظریه اطلاعات شناخته می‌شود.

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

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

در کدگذاری شانون، نمادها به ترتیب از پراحتمال‌ترین به کم‌احتمال‌ترین مرتب می‌شوند و با گرفتن اولین $l_{i}=\left\lceil {-\log }p_{i}\right\rceil$ رقم از نمایش دودویی از احتمال تجمعی $\sum \limits _{k=1}^{i-1}p_{k}$ دارای کدکلمه‌ای (codeword) می‌شوند. در اینجا $\left\lceil x\right\rceil$ بیانگر تابعی است که $x$ را رو به بالا گرد می‌نماید.

تاریخچه

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

در همین حین، کلود شانون که از محققان پیشرو در زمینه‌ی کدگذاری بود نظریه‌ی کدگذاری بدون نویز شانون (Shannon’s noiseless coding theorem) و پس از آن نظریه آنتروپی خود (Shannon’s entropy Theorem) را ارائه نمود که علاوه بر کاربرد در این مسئله‌ی آن روز دنیا، پایه مناسبی برای ادامه رشد نظریه اطلاعات شد.

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

یک مثال

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

ai	p(ai)	li	Sum from pi to i-1	Sum to p(ai) binary	Result (truncated significand)
a1	0.36	2	0.0	0.0000	00
a2	0.18	3	0.36	0.0100	010
a3	0.18	3	0.54	0.1000	100
a4	0.12	4	0.72	0.1011	1011
a5	0.09	4	0.84	0.1101	1101
a6	0.07	4	0.93	0.1110	1110