نظریه اطلاعات و کدگذاری. قضیه مستقیم شانون برای منبع شکل کلی

برای استفاده موثرکانال (با افزایش ضریب بار λ→1)، لازم است آن را با منبع اطلاعات در ورودی هماهنگ کنید. چنین تطبیقی ​​برای هر دو کانال بدون تداخل و با تداخل ممکن است، بر اساس قضایای کدگذاری کانال ارائه شده توسط شانون.

قضیه کدگذاری برای یک کانال بدون تداخل.

اگر منبع پیام دارای ظرفیت [bit/sec] و کانال ارتباطی دارای ظرفیت [bit/sec] باشد، می‌توانید پیام را به گونه‌ای رمزگذاری کنید که اطلاعات را به صورت دلخواه از طریق کانال ارتباطی با سرعت متوسط ​​ارسال کند. نزدیک به مقدار است، اما از آن تجاوز نکنید.

شانون همچنین روشی را برای چنین کدگذاری پیشنهاد کرد که به آن کدگذاری بهینه می گفتند. ایده چنین کدگذاری بعداً در آثار فانو و هافمن توسعه یافت. در حال حاضر چنین کدهایی در عمل به طور گسترده مورد استفاده قرار می گیرند (کدنویسی کارآمد و بهینه).

قضیه کدگذاری مستقیم شانون برای یک کانال نویزدار.

برای هر عملکرد منبع پیام [bit/sec] کمتر از توان عملیاتی [bit/sec]، یک روش کدگذاری وجود دارد که امکان انتقال تمام اطلاعات ایجاد شده توسط منبع پیام را با احتمال خطای دلخواه ناچیز ε فراهم می‌کند.

قضیه کدگذاری معکوس برای یک کانال نویزدار.

هیچ روش کدگذاری وجود ندارد که اجازه دهد اطلاعات با هر گونه احتمال خطا در صورتی که عملکرد منبع پیام بیشتر باشد منتقل شود. پهنای باندکانال

اثبات قضیه کدگذاری برای یک کانال با نویز از نظر ریاضی بسیار طولانی است، بنابراین ما خود را به بحث کلی در مورد جنبه های فیزیکی آن محدود می کنیم. کاربرد عملی:

1. قضیه برقرار می کند حد نظریکارایی احتمالی سیستم با انتقال مطمئن اطلاعات. از این قضیه نتیجه می گیرد که تداخل در کانال محدودیتی در دقت انتقال ایجاد نمی کند. محدودیت ها فقط بر روی سرعت انتقال اعمال می شود که در آن می توان به طور دلخواه قابلیت اطمینان انتقال بالا را به دست آورد.

در عین حال، قابلیت اطمینان کانال گسستهمعمولاً با مقدار احتمال دریافت اشتباه یک نماد تخمین زده می شود. هرچه احتمال خطا کمتر باشد، قابلیت اطمینان کانال بالاتر است. قابلیت اطمینان، به نوبه خود، مصونیت صوتی را مشخص می کند سیستم اطلاعات.

سرعت انتقال اطلاعات کارایی سیستم را مشخص می کند.

2. قضیه به موضوع راه هایی برای ساخت کدهایی که انتقال ایده آل مشخص شده را تضمین می کند، نمی پردازد. او با اثبات امکان اساسی چنین کدگذاری، تلاش های دانشمندان را برای ایجاد کدهای خاص بسیج کرد.

3. در هر سرعت متناهی از انتقال اطلاعات، تا میزان توان عملیاتی، احتمال خطای خودسرانه کمی تنها با افزایش نامحدود در مدت زمان توالی های کدگذاری شده از کاراکترها به دست می آید. بنابراین، انتقال بدون خطا در حضور تداخل تنها از نظر تئوری امکان پذیر است. حصول اطمینان از انتقال اطلاعات با احتمال خطای بسیار کم و با کارایی نسبتاً بالا در هنگام رمزگذاری توالی های بسیار طولانی از کاراکترها امکان پذیر است.

قضیه مستقیم شانون برای منبع نمای کلی نباید با دیگر قضایای شانون اشتباه شود.

قضایای شانون برای یک منبع کلیامکان رمزگذاری یک منبع کلی با استفاده از کدهای قابل تفکیک را شرح دهد. به عبارت دیگر، حداکثر قابلیت‌های کدگذاری بدون تلفات قابل دستیابی توصیف می‌شوند.

قضیه مستقیم

وقتی برای رمزگذاری حرف به حرف اعمال می شود، قضیه مستقیم را می توان به صورت زیر فرموله کرد:

برای اثبات قضیه، ویژگی های کد شانون-فانو بررسی می شود. این کدشرایط قضیه را برآورده می کند و دارای ویژگی های ذکر شده است.

قضیه مکالمه

قضیه معکوس حداکثر نسبت فشرده سازی قابل دستیابی با رمزگذاری بدون تلفات را محدود می کند. هنگامی که برای رمزگذاری حرف به حرف اعمال می شود، محدودیت در طول متوسط ​​را توصیف می کند کلمه رمزبرای هر کد قابل تفکیک

برای هر کد قابل تفکیک با طول w 1 ,w 2 ,...,w ک میانگین طول پیام بزرگتر یا مساوی با آنتروپی منبع است U، به لگاریتم باینری تعداد حروف نرمال شده است Dدر الفبای رمزگذار:

ادبیات

• گابیدولین، E. M.، Pilipchuk، N. I.§3.4 قضایای شانون برای منبع // سخنرانی‌هایی درباره نظریه اطلاعات. - م.: MIPT، 2007. - ص 49-52. - 214 ص. - شابک 5-7417-0197-3

بنیاد ویکی مدیا 2010.

ببینید «قضیه مستقیم شانون برای منبع شکل کلی» در فرهنگ‌های دیگر چیست:

نباید با دیگر قضایای شانون اشتباه شود. قضایای شانون برای یک منبع کلی، احتمالات رمزگذاری یک منبع کلی را با استفاده از کدهای قابل تفکیک توصیف می کند. به عبارت دیگر، حداکثر امکانات قابل دستیابی توصیف شده است... ... ویکی پدیا

ویکی‌پدیا مقالاتی درباره افراد دیگر با این نام خانوادگی دارد، به شانون مراجعه کنید. کلود الوود شانون کلود الوود شانون ... ویکی پدیا

کلود الوود شانون (زاده 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه ریاضی... ویکی پدیا

کلود الوود شانون (زاده 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه ریاضی... ویکی پدیا

- (انگلیسی Claude Elwood Shannon؛ متولد 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه اطلاعات ریاضی، در . .. ... ویکیپدیا

کلود الوود شانون (زاده 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه ریاضی... ویکی پدیا

کلود الوود شانون (زاده 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه ریاضی... ویکی پدیا

کلود الوود شانون (زاده 30 آوریل 1916، پتوسکی، میشیگان، میشیگان، ایالات متحده آمریکا، درگذشته 24 فوریه 2001، مدفورد، ماساچوست، ایالات متحده آمریکا) ریاضیدان و مهندس برق آمریکایی، یکی از پدیدآورندگان نظریه ریاضی... ویکی پدیا

برنامه دوره

نظریه اطلاعات و کدگذاری

سخنرانی ها در سال چهارم، ترم هفتم ارائه می شود،

51 ساعت، مدرس دانشیار

مفهوم اطلاعات، آنتروپی. سیستم های ارتباطی منابع گسسته شرح منبع با استفاده از فرآیند تصادفی. استقلال آماری منابع مارکوف ارگودیسیته. Ergodicity منبع برنولی.

استخراج فرمول آنتروپی (طبق گفته فادیف). اطلاعات متقابل و ویژگی های آن خواص آنتروپی قضیه در مورد حداکثر مقدارآنتروپی آنتروپی در واحد زمان منبع پیام.

مشکل رمزگذاری یک منبع گسسته با کدها طول مساوی. سرعت رمزگذاری مجموعه های احتمال بالا قضایای مستقیم و معکوس برای کدگذاری یک منبع گسسته با کدهایی با طول مساوی.

مشکل رمزگذاری یک منبع با کدهایی با طول نابرابر. هزینه کدنویسی کدهای بدون ابهام قابل رمزگشایی کدهای پیشوند کدنویسی حرف به حرف شرط لازم و کافی برای رمزگشایی منحصر به فرد یک کد. کدهای کامل. قضیه کدگذاری یک منبع گسسته با کدهایی با طول نابرابر. الگوریتم های ساخت کدهای بهینه (فانو، شانون، هافمن). ساخت یک کد بهینه باینری با توزیع احتمال برابر احتمالات ورودی. استفاده از تئوری اطلاعات منجر به اثبات مرزهای پایین و بالایی برای پیچیدگی پیاده سازی می شود توابع بولیدر برخی از کلاس های سیستم های کنترل روشی برای ساخت یک کد بهینه تحت شرایطی که توزیع احتمال حروف منبع ناشناخته باشد. قضیه مارکوف در مورد رمزگشایی منحصر به فرد یک کد. الگوریتم های تطبیقی ​​برای فشرده سازی اطلاعات

کانال گسسته بدون حافظه. دودویی کانال متقارن. سرعت انتقال اطلاعات در کانال ظرفیت کانال کانال گسترده و ظرفیت آن الگوهای تعیین کننده و گروه بندی مشاهدات. امکان انتقال اشتباه اطلاعات. نابرابری فاینشتاین قضیه مستقیم برای کدگذاری کانال بدون حافظه. نابرابری فانو قضیه پردازش اطلاعات. وارونگی قضیه کدگذاری.

تئوری کدگذاری مقاوم در برابر نویز معیار حداکثر احتمال فاصله کد. کدهای برابری مولد و بررسی ماتریس ها. سندرم. الگوریتم رمزگشایی برای کدهای بررسی برابری. کدهای خطیو الگوریتم رمزگشایی آنها همینگ مقید. کد همینگ کدهای چرخه ای رمزگذاری و رمزگشایی کدهای چرخه ای.

ادبیات

1. Gallagher R. نظریه اطلاعات و اتصال قابل اعتماد., M., Sov. رادیو، 1979.

2. کریچفسکی ای. سخنرانی در مورد نظریه و اطلاعات، نووسیبیرسک، NSU، 1966.

3. Kolesnik V., Poltyrev G. Course in Information Theory, Nauka, 1982.

4. Fainstein A. Fundamentals of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Error Correcting Codes, M., Mir, 1976.

6. نظریه کدگذاری جبری برلکمپ، م.، میر، 1971.

ظرفیت اطلاعات کانال های گسسته (4.4) و ظرفیت کانال های پیوسته (4.7) حداکثر قابلیت های آنها را به عنوان ابزاری برای انتقال اطلاعات مشخص می کند. آنها در قضایای بنیادی نظریه اطلاعات آشکار می شوند که به عنوان قضایای اساسی کدگذاری شانون شناخته می شوند. در رابطه با یک کانال مجزا می‌خواند:

قضیه 4.4.1. (قضیه کدگذاری مستقیم برای DKBP.)برای یک کانال مجزا بدون حافظه با نرخ کد آر، کمتر از ظرفیت اطلاعاتی، همیشه کدی وجود دارد که با افزایش طول کلمه کد، میانگین احتمال خطای آن به صفر می رسد.

در مورد یک کانال پیوسته، به صورت فرموله شده است

قضیه 4.4.2. (قضیه کدگذاری مستقیم برای کانال AWGN).در یک کانال AWGN با پهنای باند نامحدود، اگر سرعت انتقال کمتر از پهنای باند باشد، اطلاعات را می توان با احتمال خطای دلخواه کم منتقل کرد.

قضیه معکوس بیان می کند:

قضیه 4.4.3.با نرخ باد
، ظرفیت کانال ارتباطی بالاتر سی، هیچ کدی احتمال خطای رمزگشایی خودسرانه کمی را ارائه نمی دهد، یعنی. انتقال پیام کاملا قابل اعتماد

لازم به ذکر است که اگر قضیه معکوس برای مدل دلخواه یک کانال ارتباطی ثابت شود، آنگاه قضیه مستقیم فقط برای انواع خاصی از کانال ها ثابت می شود.

نتایج قضایای کدگذاری برای یک کانال نویز تا حدودی غیرمنتظره است. در واقع، در نگاه اول به نظر می رسد که کاهش احتمال خطا در انتقال پیام مستلزم کاهش متناظر در نرخ ارسال است و این دومی باید همراه با احتمال خطا به سمت صفر گرایش داشته باشد. این نتیجه به ویژه از در نظر گرفتن ارسال مجدد چندگانه نمادها در یک کانال به عنوان راهی برای کاهش احتمال خطا در انتقال پیام ناشی می شود. در این حالت، در صورت وجود تداخل در کانال ارتباطی، می توان اطمینان حاصل کرد که احتمال خطا در ارسال پیام تنها در صورتی که سرعت انتقال به صفر گرایش داشته باشد، به صفر می رسد.

با این حال، قضیه کدگذاری نشان می دهد که در اصل امکان انتقال با سرعت دلخواه نزدیک به آن وجود دارد سی، در حالی که به یک احتمال اشتباه خودسرانه کوچک دست می یابد. متأسفانه، قضایا، در حالی که وجود اساسی یک کد مقاوم در برابر خطا را نشان می دهند، دستورالعملی برای یافتن آن ارائه نمی دهند. فقط می توانیم توجه داشته باشیم که برای این کار استفاده از کدهای طولانی ضروری است. علاوه بر این، با نزدیک شدن سرعت انتقال به توان عملیاتی و کاهش احتمال خطا، به دلیل افزایش طول بلوک‌ها، کد پیچیده‌تر می‌شود که منجر به پیچیدگی شدید دستگاه‌های رمزگذاری و رمزگشایی و همچنین تأخیر در کار می‌شود. خروجی اطلاعات در حین رمزگشایی روش‌های کدگذاری کنونی مورد استفاده، که بعداً مورد بحث قرار خواهد گرفت، قابلیت‌های بالقوه سیستم ارتباطی را درک نمی‌کنند. تنها استثنا کدهای توربو اخیراً باز شده است.

1این نتیجه برای هر کانال متقارن معتبر است.

رمزگذاری اطلاعات

مفاهیم اساسی

قضایای شانون در مورد رمزگذاری پیام در بالا ذکر شد. به طور مستقیم واضح است که رمزگذاری عملیات تبدیل اطلاعات به شکل مورد نیاز برای پردازش بعدی است (انتقال از طریق کانال ارتباطی، ذخیره سازی در حافظه سیستم محاسباتی، استفاده برای تصمیم گیری و غیره). همچنین واضح است که هنگام ساختن هر سیستم اطلاعاتی، انجام بدون کدگذاری غیرممکن است: هر گونه ارائه اطلاعات مستلزم استفاده از نوعی کد است. بنابراین، ما بیشتر به تجزیه و تحلیل جزئیات خواهیم پرداخت مبنای نظریاطلاعات رمزگذاری

اجازه دهید آ- الفبای دلخواه عناصر الفبا آحروف (یا نمادها) نامیده می شوند و دنباله های متناهی که از حروف تشکیل شده اند، کلمات در نامیده می شوند آ. اعتقاد بر این است که در هر الفبای یک کلمه خالی وجود دارد که حاوی حروف نیست.

کلمه α 1 را آغاز (پیشوند) یک کلمه می گویند α ، اگر کلمه وجود داشته باشد α 2، طوری که α = α 1 α 2 ; در عین حال کلمه α 1 را شروع مناسب کلمه می گویند α ، اگر α 2 کلمه خالی نیست. طول کلمه تعداد حروف کلمه است (یک کلمه خالی دارای طول 0 است). رکورد α 1 α 2 نشان دهنده ارتباط (الحاق) کلمات است α 1 و α 2. کلمه α 2 را به پایان (پسوند) یک کلمه می گویند α ، اگر کلمه وجود داشته باشد α 1، به طوری که α = α 1 α 2 ; در عین حال کلمه α 2 را به پایان مناسب یک کلمه می گویند α ، اگر α 1 کلمه خالی نیست. یک کلمه خالی طبق تعریف ابتدا و انتهای هر کلمه در نظر گرفته می شود α .

الفبا را در نظر بگیرید ب = {0, 1, …, D- 1) که در آن D≥ 2 و یک مجموعه دلخواه سی. نمایش خودسرانه یک مجموعه سیدر بسیاری از کلمات در الفبا بتماس گرفت Dرمزگذاری مجموعه -ary سی(در D= 2 رمزگذاری باینری خواهد بود). نقشه برداری معکوس رمزگشایی نامیده می شود. بیایید نمونه هایی از رمزگذاری ها را بیان کنیم.

1. کدگذاری مجموعه اعداد طبیعی، که در آن عدد n= 0 با کلمه مطابقت دارد ه(0) = 0 و عدد n ≥ 1 کلمه باینری

ه(n) = ب 1 ب 2 … b l (n)

کوچکترین طولی که شرایط را برآورده می کند

بدیهی است که ب 1 = 1, 2ل (n) – 1 ≤ n < 2ل (n) و بنابراین

ل(n) = + 1 = ]log( n + 1)[,

جایی که [ ایکس] و ] ایکس[ نشان دهنده بزرگترین عدد صحیح است که از آن بیشتر نباشد ایکس، و کوچکترین عدد صحیح بزرگتر از ایکس. کلمه ه(n) نماد دودویی یک عدد نامیده می شود n، و این کدگذاری نمایش اعداد در است سیستم دودوییحساب کردن. این رمزگذارییک به یک است زیرا وقتی n 1 ≠ n 2 کلمه ه(n 1) و ه(n 2) متفاوت جدول 5.1 نمایش 16 عدد طبیعی اول را در سیستم اعداد باینری نشان می دهد.

جدول 5.1

کد نویسی ه(n)

n	ه(n)	n	ه(n)	n	ه(n)	n	ه(n)

2. رمزگذاری 2 اول کاعداد طبیعی، که برای هر عدد n (0 ≤ n < 2ک) با کلمه مطابقت دارد

e k(n) = 0ک – ل (n) ه(n),

جایی که ورودی 0 ک – ل (n) به کلمه ای متشکل از ک – ل(n) صفرها، ه(n) – نمایش یک عدد nدر سیستم اعداد باینری که در بالا بحث شد. این رمزگذاری برای 16 عدد طبیعی اول است ( ک= 4) در جدول 5.2 آورده شده است.

جدول 5.2

کد نویسی e k(n)

n	e k(n)	n	e k(n)	n	e k(n)	n	e k(n)

اجازه دهید آ = {یک من, من= 1، 2، ...) - الفبای متناهی یا شمارشی که حروف آن شماره گذاری شده است. اعداد طبیعی. در این مورد، رمزگذاری حروف الفبا آرا می توان با ترتیب مشخص کرد D-کلمات تحت اللفظی V = {v i, من= 1، 2، ...)، که در آن v iتصویری از یک نامه وجود دارد یک من. چنین توالی کلمات (از مجموعه V) رمزهای (الفبا) نامیده می شوند آ). اگر کد داده شود Vالفبا آ، سپس رمزگذاری کلمات، که در آن هر کلمه یک من 1 یک من 2 …یک ikبا کلمه مطابقت دارد v i 1 v i 2 …v ik، کدگذاری حرف به حرف نامیده می شود.

هنگام حرکت از کدگذاری یک به یک حروف الفبا به رمزگذاری حرف به حرف کلمات در الفبا، ممکن است ویژگی یک به یک حروف حفظ نشود. مثلا کد نویسی ه(n) ذخیره نمی کند این ملک، و کد نویسی e k(n) آن را ذخیره می کند. ویژگی یک به یک توسط کدهای قابل تفکیک حفظ می شود. کد V = {v i, من= 1, 2, …) قابل تفکیک نامیده می شود اگر از هر برابری شکل

v i 1 v i 2 …v ik = v j 1 v j 2 …vjl

به دنبال آن است ل = کو v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = vjl. به کدهای قابل تفکیک، کدهای قابل رمزگشایی منحصر به فرد نیز گفته می شود.

کدهای پیشوندی متعلق به کلاس کدهای قابل تفکیک هستند. کد V = {v i, من= 1, 2, …) در صورت عدم وجود کلمه پیشوند نامیده می شود vkآغاز (پیشوند) هیچ کلمه ای نیست v l, ل ≠ ک. اگر هر کلمه از یک کد پیشوند با کوچکترین شروع خود جایگزین شود، که شروع سایر کلمات کد نیست، کد حاصل نیز یک پیشوند خواهد بود. به این عملیات بریدن کد پیشوندی گفته می شود.

برای کد دلخواه V، شامل کلمات مختلف، می توانید یک درخت کد بسازید. این یک گراف جهت دار است که شامل چرخه هایی نیست که در آن راس وجود دارد β 1 به بالا متصل است β 2 لبه هدایت شده از β 1 به β 2 اگر و فقط اگر β 2 = β 1 ب، جایی که ب Î ب = {0, 1, …, D – 1}, D≥ 2. برای کدهای پیشوندی (و فقط برای آنها)، مجموعه کلمات رمز با مجموعه رئوس انتهایی (راسی هایی که هیچ لبه ای از آنها سرچشمه نمی گیرد) منطبق است. درخت کد.

قضایای کدگذاری اساسی

ویژگی‌های کدهایی که برای کاربرد عملی آنها مفید هستند، توسط قضایای کدگذاری اساسی تعیین می‌شوند.

قضیه 5.1. نابرابری کرافتبرای وجود یک کد منحصر به فرد قابل رمزگشایی (قابل تفکیک) حاوی نکلمات رمز در مجموعه (0, 1, D– 1) با طول n 1 , n 2 , …, n N، برای حفظ نابرابری لازم و کافی است

اثباتبیایید تصور کنیم که یک درخت کد برای یک کد پیشوند داریم. ریشه درخت کد سطح 0، رئوس مرتبط با فرم ریشه سطح 1 و غیره را تشکیل می دهد. تعداد ممکن رئوس در هر کسطح -ام را به عنوان نشان می دهیم Dk. هر قله کسطح دقیقا تخم ریزی می کند Dn – کقله ها nسطح -ام

n 1 ≤ n 2 ≤…≤ n N = n.

بدیهی است که کلمه رمز طول کدقیقا ممنوع می کند Dn – کرئوس انتهایی ممکن (رئوس آخرین سطح). سپس تمام کلمات رمزی کد پیشوند، رئوس انتهایی را ممنوع می کنند. زیرا تعداد کلرئوس انتهایی برابر هستند Dn، پس نابرابری درست است

,

که از آن نتیجه می شود که

بنابراین، نابرابری کرافت ثابت می شود.

در نتیجه اثبات قضیه 5.1، این نتیجه حاصل می شود که حداقل کدهای پیشوندی وجود دارند که کدهای منحصر به فرد قابل رمزگشایی با طول کلمه رمز هستند. n 1 , n 2 , …, n N، نابرابری کرافت را ارضا می کند. قضیه زیر که عبارت مک میلان نام دارد تعمیم می یابد این نتیجه گیریبرای همه کدهای منحصر به فرد قابل رمزگشایی

قضیه 5.2. نابرابری مک میلانهر کد منحصر به فرد قابل رمزگشایی نابرابری کرافت را برآورده می کند.

اثباتبیایید جمع را به توان برسانیم L:

. (5.1)

اجازه دهید A k- تعداد ترکیبات حاوی Lکلمات رمز با طول کل ک. سپس عبارت (6.1) را می توان به صورت نمایش داد

,

جایی که Lحداکثر - حداکثر طولپیام های حاوی Lکلمات رمزی اگر کد به طور منحصر به فرد قابل رمزگشایی است، پس همه دنباله ها از Lکلمات رمز با طول کل کمتفاوت هستند. از آنجایی که فقط وجود دارد Dkتوالی های ممکن، پس A k ≤ Dkو سپس

زیرا Lتعداد کلمات رمز مستقلی است که برای ساختن تمام دنباله‌های ممکن با طول استفاده می‌شوند Lحداکثر از همین رو L ≤ Lحداکثر و . و از این نتیجه می شود که

از آنجایی که استدلال فوق برای هر کد منحصر به فرد قابل رمزگشایی معتبر است، و نه فقط برای کدهای پیشوند، گفته مک میلان ثابت شده است.

قضایای زیر به آنتروپی یک منبع پیام و طول متوسط ​​یک کلمه رمز مربوط می شود.

قضیه 5.3. قضیه کدگذاری منبع I.برای هر منبع گسسته بدون حافظه ایکسبا الفبای متناهی و آنتروپی اچ(ایکس) وجود دارد D-ایچنی کد پیشوند، که در آن میانگین طول کلمه رمز نابرابری را برآورده می کند

. (5.2)

اثباتاول از همه، اجازه دهید آن را روشن کنیم منبع گسستهبدون حافظه، توسط مدلی توصیف می شود که ارتباطات بین نمادهای پیام را در نظر نمی گیرد. اکنون سمت چپ نابرابری (6.2) را ثابت می کنیم:

برای انجام این کار، از تعریف آنتروپی و نابرابری کرافت استفاده می کنیم:

برای اثبات سمت راست نابرابری (6.2)، نابرابری کرافت را به شکل زیر بازنویسی می کنیم:

.

سپس برای هر جمله کوچکترین عدد صحیح را انتخاب می کنیم n من، که در آن

از آنجایی که نابرابری کرافت با این انتخاب ثابت می ماند، می توانیم کد پیشوند مربوطه را بسازیم. زیرا n منکوچکترین عدد صحیح است، سپس برای n من- 1 منصفانه است

بنابراین، قضیه کدگذاری منبع I ثابت می شود. تعیین می کند که طول متوسط ​​یک کلمه رمز نمی تواند کمتر از آنتروپی منبع پیام باشد. توجه داشته باشید که اثبات قضیه از همان نمادی استفاده می‌کند که هنگام در نظر گرفتن نابرابری کرافت.

قضیه 5.4. قضیه کدگذاری منبع دوم.برای طول بلوک Lوجود دارد Dکد پیشوند -ary که در آن میانگین طول یک کلمه رمز در هر کاراکتر نابرابری را برآورده می کند

,

جایی که .

اثباتدر اینجا، بلوک های شخصیت و اچ(ایکس 1 , ایکس 2 , …, ایکس L) آنتروپی منبع پیام در هر بلوک است Lشخصیت ها. برای اثبات قضیه می توانید از قضیه کدگذاری منبع I استفاده کنید:

علاوه بر این، از آنجایی که حداقل طول قابل دستیابی یک کلمه رمز در هر نماد مقدار است، پس چه زمانی D= 2 افزونگی کد را می توان با فرمول تعیین کرد .

1 | |