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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

اثر به وب سایت اضافه شد: 1395/03/30

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. کدگذاری اطلاعات

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. مفاهیم اولیه

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

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

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

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

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

e (n) = b 1 b 2 … b l (n)

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

واضح است که b 1 = 1، 2 l (n) 1 ≤ n< 2 l (n ) و بنابراین

l(n) = + 1 = ]log(n + 1)[،

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

" xml:lang="ru-RU" lang="ru-RU">جدول 5.1

" xml:lang="ru-RU" lang="ru-RU"> کدگذاری" xml:lang="en-US" lang="en-US">e" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

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

e k (n) = 0 k l (n) e (n)،

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

" xml:lang="ru-RU" lang="ru-RU">جدول 5." xml:lang="en-US" lang="en-US">2

" xml:lang="ru-RU" lang="ru-RU"> کدگذاری" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0000	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">0100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">0001	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">0101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">0010	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">0110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">0011	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">0111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

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

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

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

نتیجه می شود که l = k و v i 1 = v j 1، v i 2 = v j 2، ...، v ik = v jl . به کدهای قابل تفکیک، کدهای قابل رمزگشایی منحصر به فرد نیز گفته می شود.

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

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

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

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

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

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

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

بدیهی است که کلمه رمز طولک دقیقا ممنوع می کند D n k رئوس انتهایی ممکن (رئوس آخرین سطح). سپس تمام کلمات کد کد پیشوند رئوس انتهایی را ممنوع می کنند. زیرا تعداد کلرئوس انتهایی برابر هستند 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 ≤ D k و سپس

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

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

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

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

. (5.2)

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

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

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

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

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

سپس

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

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

جایی که.

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

قضیه کدگذاری منبع II به ما اجازه می دهد تا بیان کنیم که روش های کدگذاری برای یک پیام به اندازه کافی طولانی وجود دارد که طول متوسط ​​کلمه کد را می توان به طور دلخواه نزدیک به مقدار آن ساخت. در واقع، وقتی L  ∞، H L (X)  H، که در آن H آنتروپی منبع پیام در هر کاراکتر، نابرابری زیر درست است:

, (5.3)

جایی که. این را می توان به صورت زیر نیز تفسیر کرد: برای هر تعداد دلخواه کوچکε ، روشی برای رمزگذاری بلوک های حاوی نمادها وجود دارد که در آن نابرابری (5.3) برای میانگین طول کلمه رمز در هر نماد وجود دارد.

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

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. رمزگذاری بهینه

مشکل ساخت کد بهینه یافتن اعداد صحیح مثبت است n 1، n 2، …، n N ، به حداقل رساندن طول متوسط ​​کلمه رمز در مورد نابرابری کرافت:

هنگام ساخت کدها در مورد الفبا A = (a i، i = 1، 2، …، N ) با توزیع احتمال شناخته شده P = ( p i، i = 1، 2، …، N ) بدون از دست دادن کلیت می توان فرض کرد که حروف الفباآ به ترتیب نزولی احتمالات شماره گذاری می شوند، یعنی. p 1 ≥ p 2 ≥ … ≥ p N . علاوه بر این، ما فقط کدهای باینری را در نظر خواهیم گرفت.

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

روش شانون تنها زمانی قابل اجرا است که همه احتمالات مثبت باشند. این شامل این واقعیت است که نامهیک من ، که احتمال دارد p i > 0، دنباله ای از n i = ] log (1/ p i )[ اولین ارقام بعد از نقطه کسری از تجزیه یک عدد به کسری نامتناهی (برای a 1 فرض می کنیم که q 1 = 0). از کی تا حالا l > k (با توجه به این واقعیت است که p l ≤ p k ) n l ≥ n k و سپس کد به دست آمده از این طریق پیشوند است. بر اساس کد پیشوند دریافتی، یک کد پیشوند کوتاه شده ساخته می شود که حاصل کدگذاری به روش شانون است.

مثلاً مجموعه ای از حروف وجود داشته باشد A = ( a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ) با توزیع احتمالپ = (0.2، 0.2، 0.19، 0.12، 0.11، 0.09، 0.09). بیایید حروف را با استفاده از روش Fano رمزگذاری کنیم.

1. بیایید لیست را به دو قسمت تقسیم کنیم تا مجموع احتمالات حروف موجود در آنها تا حد امکان با یکدیگر تفاوت داشته باشد:

A 1 = (a 1، a 2، a 3)، P 1 = (0.2، 0.2، 0.19);

A 2 = (a 4، a 5، a 6، a 7)، P 2 = (0.12، 0.11، 0.09، 0.09).

2. اجازه دهید علامت 0 را به حروف قسمت اول و علامت 1 را به حروف قسمت دوم اختصاص دهیم.

A 1 = (a 1/0، a 2/0، a 3/0) ;

A 2 = (a 4/1، a 5/1، a 6/1، a 7/1).

3. به ترتیب تکرار کنید اقدامات مشخص شدهبرای هر قسمت جداگانه که دردر نتیجه دریافت می کنیم:

A 1 1 = (a 1/00);

A 121 = (a 2/010);

A 122 = (a 3/011)؛

A 211 = (a 4/100)؛

A 212 = (a 5/101)؛

A 221 = (a 6/110)؛

A 222 = (a 7/111).

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

فرآیند کدگذاری با استفاده از روش فانو به راحتی در قالب یک جدول ارائه شده است. برای مثال مورد بررسی، در جدول 5.3 نشان داده شده است.

" xml:lang="ru-RU" lang="ru-RU">جدول 5.3

" xml:lang="ru-RU" lang="ru-RU"> کدنویسی با استفاده از روش Fano

" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0.20	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU"> 0	" xml:lang="ru-RU" lang="ru-RU"> 00
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">2	" xml:lang="ru-RU" lang="ru-RU">0.20		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">010
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">3	" xml:lang="ru-RU" lang="ru-RU">0.19			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">011
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">4	" xml:lang="ru-RU" lang="ru-RU">0.12	" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">100
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">5	" xml:lang="ru-RU" lang="ru-RU">0.11			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">101
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">6	" xml:lang="ru-RU" lang="ru-RU">0.09		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">110
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">7	" xml:lang="ru-RU" lang="ru-RU">0.09			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">111

بیایید میانگین طول کلمه رمز را تعیین کنیم:

حالا بیایید کدگذاری را با استفاده از روش شانون انجام دهیم. فرآیند کدگذاری در جدول 5.4 آورده شده است.

" xml:lang="ru-RU" lang="ru-RU">جدول 5.4

" xml:lang="ru-RU" lang="ru-RU"> کدنویسی با استفاده از روش شانون

" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">n;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">q;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">کد" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">کد کوتاه شده" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="en-US" lang="en-US">]2.321…[ = 3	" xml:lang="en-US" lang="en-US">0	000	000
a2	]2.321…[ = 3	0.2	001	001
a3	]2.395…[ = 3	0.4	011	01
a4	]3.058…[ = 4	0.59	1001	100
a5	]3.183…[ = 4	0.71	1011	101
a6	]3.472…[ = 4	0.82	1101	110
a7	]3.472…[ = 4	0.91	1110	111

مانند مورد قبلی، میانگین طول کلمه رمز را پیدا می کنیم:

.

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

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

1. ترتیب: حروف به ترتیب احتمالاتشان نزولی مرتب می شوند.

2. کاهش: دو حرف با کمترین احتمال در یکی با احتمال کل ترکیب می شوند. لیست حروف مطابق مرحله 1 مرتب می شود. این روند تا زمانی ادامه می یابد که همه حروف در یک ترکیب شوند. در این حالت، می توان با استفاده از استراتژی زیر به یکسان سازی طول کلمات رمز دست یافت: اگر چند حرف احتمالات یکسانی دارند، آن دو تا از آنها را که قبلاً کمترین تعداد ترکیب را داشتند با هم ترکیب کنید (البته این تأثیری بر روی طول کد متوسط).

3. کدگذاری: با شروع از آخرین ترکیب، نماد 0 به ترتیب به یک جزء از حرف مرکب و نماد 1 به دوم اختصاص داده می شود. این روند تا زمانی ادامه می یابد که تمام حروف اصلی رمزگذاری شوند.

اجازه دهید کدگذاری را با استفاده از روش هافمن برای مجموعه در نظر گرفته شده در مثال های استفاده از روش های فانو و شانون انجام دهیم.

1. فهرست اولیه حروفآ = { آ1 , آ2 , آ3 , آ4 , آ5 , آ6 , آ7 ) از قبل سفارش داده شده استپ = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. بیایید حروف را با هم ترکیب کنیمآ6 وآ7 در یک حرفآ1 با احتمال0.18 ودوباره سفارش دهیدفهرست:

پ1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, آ1 = { آ1 , آ2 , آ3 , آ1 , آ4 , آ5 }.

3. مرحله 2 را تکرار کنید تا یک حرف در لیست باقی بماند:

پ2 = {0.23, 0.2, 0.2, 0.19, 0.18}, آ2 = { آ2 , آ1 , آ2 , آ3 , آ1 };

پ3 = {0.37, 0.23, 0.2, 0.2}, آ3 = { آ3 , آ2 , آ1 , آ2 };

پ4 = {0.4, 0.37, 0.23}, آ4 = { آ4 , آ3 , آ2 };

پ5 = {0.6, 0.4}, آ5 = { آ5 , آ4 };

پ6 = {1}, آ6 = { آ6 }.

4. مناسب کنیمدودوییکدهانمادها:

آ6 : آ5 = 0, آ4 = 1;

آ5 : آ3 = 00, آ2 = 01;

آ4 : آ1 = 10, آ2 = 11;

آ3 : آ3 = 000, آ1 = 001;

آ2 : آ4 = 010, آ5 = 011;

آ1 : آ6 = 0010, آ7 = 0011.

بنابراین، کدهای باینری زیر به حروف اولیه اختصاص داده می شوند:آ1 = 10, آ2 = 11, آ3 = 000, آ4 = 010, آ5 = 011, آ6 = 0010, آ7 = 0011، که طول کد متوسطی را نشان می دهد که کمتر از مورد کدگذاری Fano و Shannon است.

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

.

سپس کدها دارای افزونگی زیر هستند:

کد فانو: ;

کد شانون: ;

کد هافمن: .

بنابراین، افزونگی کد هافمن حداقل است.

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

صفحه 43

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

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

اثبات قضیه.اجازه دهید H(x)و H(x|y) -آنتروپی پیشینی و پسینی در هر نماد (از انتهای دریافت کننده) برای سیستمی که توان عملیاتی را اجرا می کند باکانال با توجه به اموال Eبرای مدت زمان کافی طولانی ( پنمادها) انتقال، همه موارد ممکن از هر گروهی در گروه های بسیار محتمل و بعید قرار می گیرند. در این مورد، می توان عبارات زیر را در مورد تعداد سیگنال ها در گروه های مربوطه بیان کرد:

الف) گروهی از سیگنال های ارسالی بسیار محتمل شامل حدود 2 عدد است pN(x)دنباله ها

ب) گروهی از سیگنال های دریافتی با احتمال زیاد حاوی حدود 2 است pN(y)دنباله ها

ج) هر سیگنال دریافتی با احتمال زیاد می تواند (با احتمالات تقریباً مساوی) از حدود 2 باشد pN(x | y)سیگنال های ارسالی یک گروه با احتمال بالا

د) هر سیگنال ارسالی از یک گروه با احتمال بالا می تواند (با احتمالات تقریباً مساوی) با تقریباً 2 مطابقت داشته باشد. pN(y | x)سیگنال های احتمال بالایی دریافت کرد.

با توجه به اموال Eآنتروپی فرآیندهای گسسته، با افزایش پهمه e و d متناظر به صفر تمایل دارند.

اجازه دهید اکنون اطلاعات از طریق همان کانال با سرعت ورودی برابر با ارسال شود ن< С. در این مورد، تعداد سیگنال های بسیار محتمل ارسال شده با طول پکاراکترها برابر با 2 خواهند بود پ.ن< 2pN(x). همانطور که قبلا ذکر شد، مشکل انتخاب است کد خاصشامل نشان دادن کدام یک از 2 است pN(x)دنباله های ممکن به عنوان 2 انتخاب می شوند پ.نمجاز برای حمل و نقل و نحوه تقسیم آنها به 2 پ.نزیر گروه 2 pN(y)دنباله های خروجی بیایید کلاس همه کدهای ممکن را در نظر بگیریم که اگر 2 به دست می آیند پ.نبه دنباله ها اجازه ارسال داده شد به صورت تصادفی در میان 2 pN(x)سیگنال های احتمالی یک گروه با احتمال بالا؛ بیایید میانگین احتمال خطای این کدها را پیدا کنیم.

اجازه دهید مقداری سیگنال دریافت شود در k.احتمال خطا برابر با احتمال این است که یک سیگنال داده شده می تواند از بیش از یکی از 2 برسد. پ.نسیگنال های مجاز از آنجایی که کد با انتخاب تصادفی (به همان اندازه احتمالی) به دست می آید 2 پ.ندنباله های 2 pN(x)، سپس این احتمال وجود دارد که سیگنال داده شدهدر ورودی کانال در بین موارد مجاز برابر با

سیگنال دریافت کرد y kمربوط به 2 است pN(x | y)احتمالا سیگنال ارسال شده است از این رو میانگین احتمال این است که هیچ یک از 2 pN(x | y)سیگنال ها (به جز یک مورد واقعا ارسال شده) مجاز نیست، برابر است با (غفلت از وحدت در مقایسه با pN(x|y))

این میانگین احتمال یک دریافت بدون خطا است. بعد، از زمان ن< С = Н(х) – Н(х| у), که

N – N(x) = - N(x| y) -ساعت , (8.23)

جایی که h > 0. با جایگزینی (8.23) به (8.22)، دریافت می کنیم

می توان نشان داد که

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

توجه داشته باشید که برابری (8.25) برای هر h مثبت، هر چند کوچک، معتبر است. این بدان معنی است که قضیه شرط را می پذیرد N £ S.

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

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

قضیه.تحت شرط H £ C، در میان کدهایی که (طبق قضیه اول) احتمال خطای خودسرانه کوچکی را ارائه می دهند، کدی وجود دارد که در آن نرخ انتقال اطلاعات R به طور دلخواه نزدیک به نرخ تولید اطلاعات H است.

نرخ انتقال اطلاعات (در هر نماد) به صورت تعریف شده است

R = H – H(x|y)، (8.26)

جایی که H(x|y) -آنتروپی خلفی سیگنال ارسالی در هر نماد، یا پراکندگی اطلاعاتدر کانال

اثبات قضیه (نگاه کنید به ) با این جمله شروع می شود که حداقل افزونگی لازم برای هر نماد برابر است با H(x|y)شخصیت های اضافی آنها همچنین نشان می دهند که کد را می توان طوری انتخاب کرد که H(x|y)خودسرانه کوچک بود

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

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

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

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

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

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

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

بنابراین، قضایای داده شده، قضایای وجود هستند.

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

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

قضیه.اگر سرعت ایجاد اطلاعات H بیشتر از توان عملیاتی کانال C باشد، هیچ کدی نمی تواند احتمال خطا را به اندازه دلخواه کوچک کند. حداقل پراکندگی اطلاعات در هر نماد قابل دستیابی در H > C برابر است با H – C. هیچ کدی نمی تواند پراکندگی اطلاعات کمتری را فراهم کند.

اثبات قضیه معکوس شانون را می توان در اینجا یافت.

قضیه معکوس بیان می کند که وقتی H > Cانتقال بدون خطا امکان پذیر نیست. علاوه بر این، این نسبت بیشتر است N/C،عدم قطعیت باقیمانده بیشتر است H(x|y).مورد دوم با احتمال خطا در هنگام دریافت همراه است. این سؤال به طور طبیعی در مورد چگونگی دستیابی به حداقل احتمال خطا مطرح می شود بهترین کدنویسی، با نگرش N/Sبرای کانال باینریراه حل در داده شده است. در k = N/C< 1 вероятность ошибки e(به) = 0 طبق قضیه اول. در به® ¥ e( به) ® 0.5، به این معنی که نسبت اطلاعات منتقل شدهکل ورودی کانال به صفر میل می کند به® ¥; هرچه سرعت انتقال بیشتر باشد، اطلاعات کمتری منتقل می شود.

کنترل سوالات

1. برای نیاز به معرفی افزونگی هنگام کدنویسی در یک کانال پر سر و صدا، دلیلی منطقی ارائه دهید.

2. میانگین مقدار اطلاعات (به ازای هر کاراکتر) چگونه منتقل می شود کانال گسستهبا سر و صدا؟

3. سرعت و ظرفیت انتقال یک کانال نویز چگونه تعیین می شود؟

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

5. چه روابطی از قضیه در مورد همسانی احتمال مجانبی زنجیره های معمولی به اندازه کافی بلند برای کانال های ثابت با نویز به دست می آید؟

6. دلیل کدگذاری دنباله های طولانی کاراکترها چیست؟

7. چه فرمولی ظرفیت یک کانال متقارن باینری بدون حافظه را تعیین می کند، در چه شرایطی ظرفیت این کانال از بین می رود؟

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

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

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

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

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

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

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

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

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

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

برنامه دوره

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

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

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

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

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

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

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

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

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

ادبیات

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.