مقدمه گرایش‌های جدیدی که در قرن بیستم در ریاضیات پدید آمده‌اند، معمولاً با مفاهیم و مفاهیم پیچیده‌ای عمل می‌کنند که رایج کردن آنها دشوار است. در مقابل این زمینه، شایستگی ریاضیدان و مهندس برجسته آمریکایی کلود شانون، که در سالهای 1947-1948، بر اساس ملاحظات ابتدایی، کشف کرد. منطقه جدیدریاضیات - نظریه اطلاعات. انگیزه ایجاد علم جدیدتمیز بودند مشکلات فنیانتقال اطلاعات از طریق سیم های تلگراف و تلفن، اما به دلیل ماهیت کلی آن، نظریه اطلاعات در حال حاضر در تحقیقات مربوط به انتقال و ذخیره هر گونه اطلاعات در طبیعت و فناوری استفاده می شود. در پایان دهه چهل، در طلوع توسعه نظریه اطلاعات، ایده توسعه جدید راه های موثراطلاعات کدگذاری در هوا بود. محققان با مسائل آنتروپی، محتوای اطلاعاتی و افزونگی سروکار داشته اند. من تعجب می کنم اینها چیست کارهای اولیهدر زمینه فشرده سازی اطلاعات قبل از ظهور رایانه های دیجیتال مدرن انجام شد. امروزه تئوری اطلاعات به موازات برنامه نویسی در حال توسعه است، اما در آن زمان ایده توسعه الگوریتم هایی با استفاده از محاسبات دودویی برای رمزگذاری کاراکترها گام مهمی به جلو بود. الگوریتم های شانون - فانو و هافمن یکی از اولین الگوریتم ها برای کدگذاری کارآمد اطلاعات بودند. این مقاله در نظر گرفته است مفاهیم اساسیآنتروپی و اطلاعات و همچنین تشریح اصول رمزگذاری پیام ها از نظر شانون - فانو و هافمن، نقش مهم آنها را در انتقال اطلاعات از طریق خطوط ارتباطی نشان می دهد. اما خطوط ارتباطی که این روش‌های رمزگذاری اطلاعات برای آنها ایجاد شده‌اند، در گذشته هستند. خوشبختانه، اصول شانون-فانو و هافمن در آن اعمال شده است دنیای مدرن: برای فشرده سازی اطلاعات. آرشیوهای PKZIP، ARJ، و همچنین بخشی از استاندارد معروف JPEG (فشرده سازی اطلاعات گرافیکی با ضرر) دقیقاً بر روی این اصول کار کنید. کدهای شانون فانو و هافمن در تمامی دانشگاه های فنی دنیا تدریس می شود و علاوه بر آن در برنامه تحصیل پیشرفته علوم کامپیوتر در مدرسه نیز گنجانده شده است. بنابراین مطالعه روش های کدگذاری شانون - فانو و هافمن مرتبط است. هدف از این کار بررسی اصول کدگذاری اطلاعات شانون - فانو و هافمن و کاربرد آنها در حل مسائل می باشد. کار مطالعه آنتروپی و افزونگی انواع خاصی از پیام ها برای کاربرد بعدی اصول شانون-فانو و هافمن در آنها است. 1. اطلاعات و کدگذاری. کدهای شانون - فانو و هافمن. 1.1 اطلاعات و کدگذاری. کلمه "اطلاعات" در زمان ما برای همه شناخته شده است. این از لاتین "informatio" می آید، که به معنای - شفاف سازی، پیام، آگاهی است. با این حال، چندی پیش، در اواسط قرن بیستم، به پیشنهاد کلود شانون، به طور مداوم مورد استفاده قرار گرفت. وی این اصطلاح را به معنای فنی محدود در رابطه با نظریه ارتباط یا انتقال رمزها معرفی کرد که به آن «نظریه اطلاعات» می گفتند. در اینجا، هیچ اطلاعاتی مهم نیست، بلکه فقط اطلاعاتی هستند که به طور کامل عدم اطمینان موجود را حذف یا کاهش می دهند. یکی از بنیانگذاران علوم کامپیوتر، دانشمند مشهور آمریکایی، نوربرت وینر، یک تعریف فلسفی و در نتیجه گسترده‌تر از این اصطلاح ارائه می‌کند: «اطلاعات تعیین محتوایی است که ما از دنیای خارج در فرآیند انطباق با آن می‌گیریم. و تفکر خود را با آن هماهنگ کنیم." البته، اینها با تعاریف منحصربفرد اطلاعات فاصله زیادی دارند. در حال حاضر، این اصطلاح معنای عمیق تر و چند وجهی بیشتری دارد. با باقی ماندن تا حد زیادی شهودی، محتوای معنایی متفاوتی را در شاخه های مختلف فعالیت انسانی دریافت می کند: * در جنبه روزمره، اطلاعات به عنوان اطلاعاتی در مورد جهان اطراف و فرآیندهای در حال وقوع در آن درک می شود که توسط یک شخص یا دستگاه های خاص درک می شود. * در فناوری، اطلاعات به عنوان پیام هایی درک می شود که به شکل علائم یا سیگنال ها منتقل می شوند. * در تئوری اطلاعات (طبق نظر K. Shannon)، هیچ اطلاعاتی مهم نیست، بلکه فقط اطلاعاتی هستند که به طور کامل عدم قطعیت موجود را حذف یا کاهش دهند. * در نظریه معنایی (معنای پیام) - این اطلاعاتی است که تازگی دارد و غیره... چنین رویکردهای متنوع تصادفی نیست، بلکه نتیجه این واقعیت است که نیاز به سازماندهی آگاهانه فرآیندهای حرکت و پردازش آنچه دارای نام مشترک است - اطلاعات پدیدار شده است. برای بررسی بیشتر، به مفهوم اطلاعات نیاز داریم که به معنای انتقال پیام های اطلاعاتی از طریق خطوط ارتباطی است. در نظر گرفتن طرح کلیانتقال پیام؛ برای قطعیت، مثلاً از تلگراف صحبت خواهیم کرد. در یک انتهای خط، فرستنده پیامی را ارسال می کند که با استفاده از هر یک از حروف یا اعداد شناخته شده برای ما نوشته شده است، یا هر دو حروف و اعداد با هم ترکیب شده اند. برای انتقال این نوع پیام‌ها، از توالی سیگنال‌های جریان مستقیم استفاده می‌شود که اپراتور تلگراف می‌تواند برخی از ویژگی‌های آنها را به صلاحدید خود تغییر دهد که توسط اپراتور دوم تلگراف در انتهای خط دریافت می‌شود. ساده ترین سیگنال های قابل تشخیص که به طور گسترده در عمل استفاده می شود، ارسال یک جریان است (یعنی روشن کردن آن برای برخی به طور کامل زمان مشخص) و بدون ارسال - مکث (خاموش کردن جریان برای همان زمان)؛ با کمک این دو سیگنال به تنهایی، در صورت موافقت با جایگزینی هر حرف یا عدد، می توانید هر پیامی را ارسال کنید یک ترکیب خاصارسال جریان و مکث در مهندسی ارتباطات، قاعده‌ای که هر پیام ارسال شده را با ترکیب مشخصی از سیگنال‌ها مرتبط می‌کند، معمولاً یک کد (در مورد تلگراف، یک کد تلگراف) و خود عملیات ترجمه یک پیام به یک دنباله نامیده می‌شود. سیگنال های مختلف- کدگذاری پیام یک «کد» به عنوان مجموعه‌ای از n نام کد، با n حرف الفبا مطابقت داده می‌شود، که برای آن شرط زیر برآورده می‌شود: هیچ تعیین کدی از یک حرف با ابتدای هر تعیین کد طولانی‌تری مطابقت نداشته باشد، یعنی. کدها باید به صورت یکتا رمزگشایی شوند. با این حال، کدهایی که فقط از دو تراشه مختلف استفاده می کنند (مثلاً ارسال جریان و مکث) کدهای باینری نامیده می شوند. در برخی از مجموعه های تلگراف، به جز گنجاندن سادهو با خاموش کردن جریان، می توانید جهت آن را نیز معکوس کنید. در این صورت، به جای ارسال جریان و مکث، می توان از ارسال جریان در دو جهت مختلف به عنوان سیگنال اصلی استفاده کرد یا از سه سیگنال ابتدایی مختلف با مدت زمان یکسان در یک زمان استفاده کرد - ارسال جریان در یک جهت. ارسال جریان در جهت دیگر و مکث (به این روش کدگذاری کد سه تایی می گویند). حتی دستگاه های تلگراف پیچیده تری نیز امکان پذیر است که در آنها ارسال جریان نه تنها در جهت، بلکه در قدرت جریان نیز متفاوت است. بنابراین ما این فرصت را داریم که تعداد سیگنال های ابتدایی مختلف را حتی بیشتر کنیم. افزایش تعداد سیگنال های ابتدایی مختلف به شما امکان می دهد کد را فشرده تر کنید. با این حال، هزینه سیستم انتقال را نیز پیچیده و افزایش می دهد، به طوری که کدهای تراشه پایین همچنان در این هنر ترجیح داده می شوند. اجازه دهید پیامی با استفاده از مقداری "الفبا" حاوی n "حرف" نوشته شود. برای "رمزگذاری" این پیام لازم است، به عنوان مثال. قاعده ای را نشان می دهد که هر پیامی از این قبیل را با دنباله خاصی از m "تراشه" های مختلف مرتبط می کند که "الفبای" ارسال را تشکیل می دهند. ما کدنویسی را در نظر می گیریم که سود بیشتری داشته باشد، سیگنال های اولیه کمتری برای انتقال یک پیام صرف شود. اگر فرض کنیم که هر یک از سیگنال های ابتدایی به طور یکسان طول بکشد، سودمندترین کد اجازه می دهد تا کمترین زمان برای انتقال پیام صرف شود. ملک اصلی رویدادهای تصادفیعدم اطمینان کامل در وقوع آنها است که عدم اطمینان خاصی را هنگام انجام آزمایش های مربوط به این رویدادها ایجاد می کند. اما کاملاً واضح است که میزان این عدم قطعیت در موارد مختلف کاملاً متفاوت خواهد بود. برای تمرین، مهم است که بتوانیم درجه عدم قطعیت طیف گسترده ای از آزمایش ها را به صورت عددی برآورد کنیم تا بتوانیم آنها را از این طرف مقایسه کنیم. دو تجربه مستقل و همچنین یک تجربه پیچیده متشکل از را در نظر بگیرید اجرای همزمانآزمایش ها و. اجازه دهید تجربه k نتایج مشابه داشته باشد، و تجربه دارای l پیامدهای مشابه باشد. بدیهی است که عدم قطعیت تجربه بیشتر از عدم قطعیت تجربه است، زیرا در اینجا عدم قطعیت نتیجه تجربه به عدم قطعیت اضافه می شود. طبیعی است که فرض کنیم درجه عدم قطعیت تجربه برابر با مجموع عدم قطعیت هایی است که آزمایش ها را مشخص می کند، یعنی:. فقط یک تابع شرایط را برآورده می کند، زمانی که -:. آزمایش A را در نظر بگیرید که شامل تجربیات و احتمالات است. سپس مجموع عدم قطعیت برای آزمایش A برابر خواهد بود.این عدد آخر را آنتروپی آزمایش می نامند و با نشان داده می شود. اگر تعداد حروف در "الفبا" برابر با n و تعداد سیگنال های ابتدایی استفاده شده برابر با m باشد، برای هر روش کدگذاری میانگین تعداد سیگنال های ابتدایی در هر حرف الفبا نمی تواند کمتر از آن باشد. با این حال، اگر فقط تعیین کدهای فردی فوراً با "بلوک های" به اندازه کافی طولانی که شامل تعداد زیادینامه ها. ما فقط در اینجا در نظر خواهیم گرفت ساده ترین موردپیام هایی که با استفاده از تعدادی n "حروف" نوشته شده اند، فراوانی تجلی آنها در هر نقطه از پیام کاملاً با احتمالات p1، p2، ... ...، pn مشخص می شود، که البته، p1 + p2 + ... + pn = 1، که در آن احتمال pi است تظاهرات i-thحروف در هر مکان پیام یکسان فرض می شود، صرف نظر از اینکه کدام حروف در همه مکان های قبلی بوده است، یعنی. حروف متوالی پیام مستقل از یکدیگر هستند. در واقع، در پیام های واقعی اغلب اینطور نیست. به طور خاص، در زبان روسی، احتمال ظهور یک حرف خاص به طور قابل توجهی به حرف قبلی بستگی دارد. با این حال، توجه دقیق به وابستگی متقابل حروف، همه ملاحظات بعدی را بسیار دشوار می کند، اما به هیچ وجه نتایج آینده را تغییر نخواهد داد. ما در حال حاضر به دنبال کدهای باینری خواهیم بود. تعمیم نتایج به دست آمده در این مورد برای کدهای با استفاده از شماره دلخواهسیگنال های ابتدایی t، مثل همیشه، بسیار ساده است. بیایید با ساده‌ترین حالت کدهایی شروع کنیم که یک کد جداگانه - دنباله‌ای از اعداد 0 و 1 - را با هر "حرف" یک پیام مرتبط می‌کنند. هر کد دودویی برای یک الفبای n حرفی را می توان با روشی برای حدس زدن برخی از اعداد پنهان x، که از n تجاوز نمی کند، با استفاده از سؤالاتی که فقط به آنها «بله» (1) یا «نه» (0) پاسخ داده شده است، مرتبط کرد که ما را راهنمایی می کند. به کد باینری برای احتمالات داده شده p1، p2، ...، pn حروف جداگانه، ارسال یک پیام چند حرفی مقرون به صرفه ترین کد خواهد بود که با این احتمالات n مقدار x، مقدار متوسط تعداد سؤالات را نشان می دهد. سؤال شده (علائم باینری: 0 و 1 یا سیگنال های ابتدایی) کوچکترین است. اول از همه، میانگین تعداد سیگنال های ابتدایی باینری در پیام رمزگذاری شده در هر حرف از پیام اصلی نمی تواند کمتر از H باشد، که در آن H = - p1 log p1 - p2 log p2 - ... - pn log pn آنتروپی است. تجربه ای که شامل تشخیص یک حرف از متن (یا به طور خلاصه فقط آنتروپی یک حرف) است. از اینجا بلافاصله نتیجه می شود که برای هر روش کدگذاری، برای نوشتن یک پیام طولانی از حروف M، حداقل MH کاراکترهای باینری مورد نیاز است و به هیچ وجه نمی تواند از یک بیت تجاوز کند. اگر احتمالات p1، p2، ... ...، pn همه با هم برابر نباشند، H< log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв. 1.2 Коды Шеннона - Фано. Для удобства расположим все имеющиеся п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы - верхнюю и нижнюю - так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы - цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве. Такой метод кодирования сообщений был впервые предложен в 1948 - 1949 гг. независимо друг от друга Р. Фано и К. Шенноном; поэтому соответствующий код обычно называется кодом Шеннона - Фано. Так, например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы. № буквывероят-ностьразбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)кодовое обозначение10,4} I 120,2} II} I 0130,2} II} I 00140,1} II} I 000150,05} II} I0000160,05} II00000 Табл.1 Аналогично предыдущему примеру разобран случай "алфавита", включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2) № буквывероят-ностьразбиение на подгруппы кодовое обозначение10,3} I} I 1120,2} II 1030,1} II} I} I 01140,1} II} I 010150,05} II 010060,03} II} I} I} I 0011170,03} II 0011080,03} II} I 0010190,03} II 00100100,03} II} I} I 00011110,02} II} I 000101120,02} II 000100130,01} II} I} I 000011140,01} II} I0000101150,01} II0000100160,01} II} I 000001170,01} II} I0000001180,01} II0000000 Табл.2 Основной принцип, положенный в основу кодирования по методу Шеннона - Фано, заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в نامگذاری های مختلفدر این مورد، معلوم می شود که متفاوت است (به ویژه، در نمونه دوم مورد تجزیه و تحلیل از دو تا هفت متغیر است)، یعنی کد شانون - فانو غیر یکنواخت است. با این حال، درک این موضوع دشوار نیست که هیچ کدی در اینجا نمی تواند آغاز یک نامگذاری طولانی تر باشد. بنابراین، پیام رمزگذاری شده همیشه می تواند بدون ابهام رمزگشایی شود. در نتیجه، مقدار متوسط طول چنین تعیینی هنوز هم فقط کمی بیشتر از حداقل مقدار مجاز H با توجه به حفظ مقدار اطلاعات در طول رمزگذاری است. بنابراین، برای مثال یک الفبای 6 حرفی که در بالا در نظر گرفته شد، بهترین کد یکنواخت شامل کدهای سه رقمی است (زیرا 22< 6 < 23), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона - Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 24 < 18 < 25); в случае же кода Шеннона - Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона - Фано не отдельные буквы, а сразу целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log0,7 - 0,3 log0,3 = 0,881... Применение метода Шеннона - Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду буква вероятность кодовое обозначение А 0,7 1 Б 0,3 0 требующему для передачи каждой буквы одного двоичного знака - на 12% больше минимального достижимого значения 0,881 дв.зн./букву. Применяя же метод Шеннона - Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение АА 0,49 1 АБ 0,21 01 БА 0,21 001 ББ 0,09 000 Среднее значение длины кодового обозначения здесь равно, так что на одну букву алфавита здесь приходится в среднем двоичных знаков - лишь на 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим, применив метод Шеннона - Фано к кодированию трехбуквенной комбинации; при этом мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение ААА 0,343 11 ААБ 0,147 10 АБА 0,147 011 БАА 0,147 010 АББ 0,063 0010 БАБ 0,063 0011 ББА 0,063 0001 БББ 0,027 0000 Среднее значение длины кодового обозначения здесь равно 2,686, т.е. на одну букву текста приходится в среднем 0,895 двоичных знаков, что всего на 1,5% больше значения дв.зн./букву. В случае еще большей разницы в вероятностях букв А и Б приближение к минимально возможному значению Н дв.зн./букву может несколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А) = 0,89 и р(Б) = 0,11 это значение равно - 0,89 log0,89 - 0,11 log0,11 ≈ 0,5 дв.зн./букву, а равномерный код (равносильный применению кода Шеннона - Фано к совокупности двух имеющихся букв) требует затраты одного двоичного знака на каждую букву - в два раза больше. Нетрудно проверить, что применение кода Шеннона - Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям - 0,55, а к четырехбуквенным блокам - в среднем 0,52 двоичных знаков - всего на 4% больше минимального значения 0,50 дв.зн./букву. 1.3 Коды Хафмана. Близок к коду Шеннона - Фано, но еще выгоднее, чем последний, так называемый код Хафмана. Построение этого кода опирается на простое преобразование используемого алфавита, называемое сжатием алфавита. Пусть мы имеем алфавит А, содержащий буквы, вероятности появления которых в сообщении соответственно равны; при этом мы считаем буквы расположенными в порядке убывания их вероятностей (или частот), т.е. полагаем, что. Условимся теперь не различать между собой две наименее вероятные буквы нашего алфавита, т.е. будем считать, что ап-1 и ап - это одна и та же буква b нового алфавита А1, содержащего теперь уже буквы и b (т.е. ап-1 или ап), вероятности появления которых в сообщении соответственно равны и рп-1 + рп. Алфавит А1 и называется полученным из алфавита А с помощью сжатия (или однократного сжатия). Расположим буквы нового алфавита А1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придем к алфавиту А2, который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А1 - с помощью простого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего п - 2 буквы. Продолжая эту процедуру, мы будем приходить ко все более коротким алфавитам; после (п - 2)-кратного сжатия мы придем к алфавиту Ап-2, содержащему уже всего две буквы. Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит, содержащий 6 букв, вероятности которых равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05: № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,40,40,40,40,620,20,20,20,40,430,20,20,20,240,10,10,250,050,160,05 Табл.3 Условимся теперь приписывать двум буквам последнего алфавита Ап-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Aj, то буквам "предыдущего" алфавита Aj-1 (где, разумеется, А1-1 = А0 - это исходный алфавит А), сохранившимся и в алфавите Aj, мы пишем те же кодовые обозначения, которые они имели в алфавите Aj-1; двум же буквам a" и a"" алфавита Aj, "слившимся" в одну букву b алфавита Aj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце. (Табл.4) № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,4 00,4 00,4 0 0,4 00,6 120,2 100,2 100,2 100,4 11 0,4 030,2 1110,2 1110,2 1110,2 10 40,1 11010,1 11010,2 110 50,05 110010,1 1100 60,05 11000 Табл. 4 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет شرایط عمومی: هیچ علامت کدی در اینجا آغاز یک علامت رمز طولانی تر دیگر نیست. همچنین توجه داشته باشید که رمزگذاری یک الفبای خاص با روش هافمن (و همچنین با روش شانون - فانو) یک روش بدون ابهام نیست. بنابراین، به عنوان مثال، در هر مرحله از ساخت کد، البته می توانید عدد 1 را با عدد 0 جایگزین کنید و بالعکس. با این دو به دست می آوریم کدهای مختلف(بسیار ناچیز با یکدیگر تفاوت دارند). اما علاوه بر این، در برخی موارد، امکان ساخت چندین کد هافمن بسیار متفاوت وجود دارد. بنابراین، به عنوان مثال، در مثال جداسازی شده در بالا، می توانید یک کد مطابق با جدول زیر بسازید: تعداد حرف احتمالات الفبای اصلی الفبای فشرده A1A2A3A410.4 110.4 110.4 11 0.4 00.6 120.2 010.2 100.210.210.10.2 120.2 120.2 010.210.10.4 1000.1 1010.2 00 50.05 10110.1 100 60.05 1010 جدول 5 کد جدید همچنین یک کد هافمن است، اما طول نامگذاری کدهای موجود اکنون کاملاً متفاوت است. توجه داشته باشید که میانگین تعداد سیگنال های ابتدایی در هر حرف دقیقاً برای هر دو کد هافمن ساخته شده یکسان است: در حالت اول برابر است و در حالت دوم برابر است. می‌توان نشان داد که کد هافمن همیشه مقرون‌به‌صرفه‌ترین کد ممکن است، به این معنا که برای هیچ روش دیگری برای رمزگذاری حروف الفبای خاص، میانگین تعداد سیگنال‌های ابتدایی در هر حرف می‌تواند کمتر از آن باشد که هنگام رمزگذاری توسط روش هافمن (البته از این، بلافاصله نتیجه می شود که برای هر دو کد هافمن، میانگین طول تعیین کد باید دقیقاً یکسان باشد - هر دوی آنها مقرون به صرفه ترین هستند). استدلال ارائه شده در پاراگراف های 1.2 و 1.3 به طور کامل هنگام حل مسائل اجرا می شود (نمونه ای از چنین مشکلی در پیوست A آورده شده است). 2. آنتروپی انواع خاصی از پیام ها. 2.1 قضیه اصلی در مورد کدگذاری. درجه نزدیکی میانگین تعداد کاراکترهای باینری در هر حرف از پیام به مقدار H به دست آمده در مثال‌های در نظر گرفته شده در بالا می‌تواند به طور دلخواه با انتقال به کدگذاری بلوک‌های طولانی‌تر افزایش یابد. این از عبارت کلی زیر که در ادامه آن را قضیه کدگذاری اصلی می نامیم، به طور دقیق تر، قضیه کدگذاری اصلی در صورت عدم تداخل، نتیجه می گیرد: هنگام کدگذاری پیامی که به بلوک های حرف N تقسیم می شود، با انتخاب N به اندازه کافی بزرگ، می توانیم به این نتیجه رسیدیم که میانگین تعداد تراشه‌های باینری در هر حرف از پیام اصلی به طور دلخواه نزدیک به H است. رمزگذاری بلوک‌های طولانی به طور همزمان دارای مزایای قابل توجهی در حضور تداخلی است که عملکرد خط ارتباطی را مختل می‌کند. با توجه به اهمیت زیاد قضیه کدگذاری اصلی که در اینجا فرموله شده است، در زیر اثبات آن را بر اساس استفاده از روش کدگذاری شانون - فانو ارائه می کنیم. ابتدا فرض کنید که با روش شانون - فانو، که اساس تقسیم متوالی مجموعه حروف رمزگذاری شده (که با آن کل "بلوک ها" نیز قابل درک است) به گروه های کوچکتر و کوچکتر است، هر بار موفق می شویم اطمینان حاصل کنیم که احتمالات دو گروه حاصل دقیقاً با یکدیگر برابر است ... در این صورت، پس از تقسیم اول، به گروه هایی با احتمال کل 1/2 می رسیم، پس از دوم - به گروه هایی با احتمال کل 1/4، ...، بعد از تقسیم دوم - به گروه هایی با یک احتمال کل 1/2 لیتر. در این حالت، نام کد رقمی l دارای حروفی خواهد بود که دقیقاً پس از تقسیمات l به گروهی از یک عنصر اختصاص داده می شود. به عبارت دیگر، اگر این شرط برآورده شود، طول li نامگذاری کد با فرمول B به احتمال pi حرف مربوطه مربوط می شود. مورد کلیمقدار - log pi، جایی که pi - احتمال i-امحرف الفبا، یک عدد صحیح نخواهد بود، بنابراین طول li کد نماد i-امحروف نمی توانند برابر با log pi باشند. از آنجایی که هنگام کدنویسی با روش شانون - فانو، الفبای خود را به صورت متوالی به گروه هایی نزدیک به احتمال کل تقسیم می کنیم، طول تعیین کد حرف i با چنین کدگذاری نزدیک به - log pi خواهد بود. در این رابطه، اولین عدد صحیح را با li نشان می دهیم که کمتر از - log pi نباشد: (الف) آخرین نابرابری را می توان به صورت زیر بازنویسی کرد: یا (ب) در اینجا توجه می کنیم که در مورد هر n عددی که نابرابری را برآورده کند، ( 1) یک کد باینری وجود دارد که این اعداد طول نامگذاری کد مرتبط با n حرف از یک الفبای خاص است. متوسط l سیگنال های باینری به ازای هر یک حرف از پیام اصلی (یا، میانگین طول تعیین کد) با مجموع داده می شود. اکنون بیایید نابرابری (A) را که مقدار li را به دست می‌دهد در پی ضرب کنیم، تمام نابرابری‌های به‌دست‌آمده از این طریق را مطابق با مقادیر i = 1، 2، ...، n جمع کنیم و در نظر بگیریم که در کجا آنتروپی آزمایش شامل تعیین یک حرف از پیام است و p1 + p2 + ... + pn = 1. در نتیجه، آن را به دست می‌آوریم. اجازه دهید این نابرابری را در موردی اعمال کنیم که روش توضیح داده شده در بالا برای رمزگذاری تمام بلوک‌های حروف N ممکن (که می‌توانند حروف الفبای جدید در نظر گرفته شوند) استفاده می‌شود. بر اساس فرض استقلال حروف متوالی پیام، آنتروپی آزمایش، که شامل تعیین تمام حروف بلوک است، در نتیجه، طول متوسط lN تعیین کد بلوک حرف N را برآورده می کند. نابرابری ها اما هنگام رمزگذاری بلوک های N-حرفی به طور همزمان، تعداد متوسط l سیگنال های ابتدایی باینری در هر حرف پیام برابر با طول متوسط lN تعیین کد یک بلوک تقسیم بر تعداد N حرف در بلوک خواهد بود. : بنابراین، با چنین کدگذاری، یعنی در اینجا میانگین تعداد سیگنال های ابتدایی در هر حرف با حداقل مقدار H بیش از آن متفاوت است. با فرض، بلافاصله به قضیه اصلی در مورد کدگذاری می رسیم. اثبات فوق را می‌توان در مورد کلی‌تر زمانی که حروف متوالی متن به یکدیگر وابسته هستند نیز اعمال کرد. در این حالت فقط لازم است نابرابری مقدار lN را به شکلی بنویسید که در آن آنتروپی بلوک حرف N است که در صورت وابستگی حروف پیام از یکدیگر همیشه کمتر خواهد بود. از NH (برای و). بنابراین، در این حالت کلی تر (با افزایش نامحدود در طول بلوک ها)، میانگین تعداد سیگنال های اولیه صرف شده برای ارسال یک حرف، به طور نامحدود به مقداری نزدیک می شود که در آن "آنتروپی خاص" وجود دارد. به ازای یک حرف از یک متن چند حرفی وجود یک حد از نابرابری‌ها ناشی می‌شود که نشان می‌دهد یک دنباله یک دنباله یکنواخت غیرافزاینده از اعداد مثبت (صفر بزرگ) است. تمام عبارات قبلی به راحتی با استفاده از سیگنال های t ابتدایی به کدهای t-ary منتقل می شوند. بنابراین، برای ساخت کدهای m-ary Shannon - Fano، فقط باید گروه های نمادها را نه به دو، بلکه به m قسمت تا حد ممکن تقسیم کرد و برای ساخت کد t-ary هافمن، باید از عملیات استفاده کرد. فشرده سازی الفبا که در آن هر بار دو عدد با هم ادغام نمی شوند و m حروف الفبای اصلی که کمترین احتمال را دارند. با توجه به اهمیت کدهای هافمن، اجازه دهید در مورد آخرین سوال با جزئیات بیشتر صحبت کنیم. فشرده سازی الفبا، که در آن حروف m با یک جایگزین می شود، منجر به کاهش تعداد حروف به میزان m - 1 می شود. از آنجایی که برای ساخت یک کد t-ary، بدیهی است که نیاز است که دنباله "انقباضات" در نهایت ما را به الفبای m از حروف (مرتبط با سیگنال های m کد) هدایت کند، لازم است که عدد n حرف از الفبای اولیه به شکل n = m + k (m - 1) قابل نمایش است، که در آن k یک عدد صحیح است. با این حال، همیشه می توان با افزودن، در صورت لزوم، چند "حروف ساختگی" دیگر به الفبای اصلی، که احتمالات آنها محاسبه می شود، به این امر دست یافت. برابر با صفر... پس از این، ساخت یک کد هافمن t-ary و اثبات بهینه بودن آن (در بین همه کدهای t-ary) دقیقاً به همان روشی که در مورد انجام شده است انجام می شود. کد باینری... بنابراین، برای مثال، در مورد الفبای 6 حرفی که قبلاً در بالا در نظر گرفته شد، که احتمالات 0.4، 0.2، 0.2، 0.1، 0.05 و 0.05 برای ساخت کد هافمن سه تایی دارند، باید یک حرف دیگر به الفبای خود اضافه کنیم. با احتمال صفر و سپس به صورت زیر عمل کنید: تعداد حروف احتمالی و کد تعیین حروف الفبای اصلی فشرده شده 10.4 00.4 00.4 020.2 20.2 20.4 130.2 100.2 100.2 240 T.2 100.2 240، 1 15010، 1 150.1 به آسانی قابل حمل است. در مورد کدهای t-ary و به اثبات بالا قضیه کدگذاری اصلی. به طور خاص، اصلاح مربوطه بر اساس این واقعیت است که هر n عدد l1، l2، ...، ln که نابرابری را برآورده کند، طول نامگذاری کد برخی از کد t-ary برای یک الفبای n حرفی است. با تکرار استدلال برای حالت m = 2، به راحتی می توان نتیجه زیر را به دست آورد (که قضیه کدگذاری اصلی برای کدهای t-ary نامیده می شود): برای هر روش کدگذاری با استفاده از کد t-ary، میانگین تعداد تراشه ها در هر حرف پیام هرگز نمی تواند کمتر از نسبت (که در آن H آنتروپی یک حرف از پیام است) باشد. با این حال، اگر "بلوک‌های" به اندازه کافی طولانی از N حروف به طور همزمان کدگذاری شوند، همیشه می‌توان به طور دلخواه به این مقدار نزدیک شد. از این رو، واضح است که اگر سیگنال‌های ابتدایی L (با گرفتن m مقادیر مختلف) را بتوان از طریق یک خط ارتباطی در واحد زمان منتقل کرد، نرخ انتقال پیام در چنین خطی نمی‌تواند بیشتر از حروف / واحد باشد. زمان؛ با این حال، انتقال با سرعت دلخواه نزدیک به v (اما کمتر از v!) در حال حاضر امکان پذیر است. مقدار در شمارش عبارت v فقط به خود خط ارتباطی بستگی دارد (در حالی که مخرج H پیام ارسال شده را مشخص می کند). این مقدار نشان می دهد بزرگترین عددواحدهای اطلاعاتی که می توانند در طول خط ما در واحد زمان منتقل شوند (زیرا همانطور که می دانیم یک سیگنال اولیه حداکثر می تواند حاوی log m واحد اطلاعات باشد). به آن پهنای باند خط ارتباطی می گویند. مفهوم پهنای باندنمایشنامه نقش مهم در تئوری ارتباطات 2.2 آنتروپی و اطلاعات انواع پیام خاص. 2.2.1 گفتار نوشتاری برای انتقال یک پیام حرف M که به m سیگنال‌های ابتدایی مختلف اجازه می‌دهد، کمتر از سیگنال‌ها صرف شود، جایی که n تعداد حروف الفبا است. از آنجایی که الفبای تلگرافی روسی حاوی 32 حرف است. (حروف e و e b و b از هم متمایز نمی شوند، اما در بین حروف حساب می شوند و "حرف صفر" فضای خالی بین کلمات است)، سپس سیگنال های ابتدایی باید برای ارسال یک پیام حرف M صرف شود. متن روسی، مشروط بر اینکه همه حروف به یک اندازه محتمل در نظر گرفته شوند. برای به دست آوردن متنی که در آن هر حرف حاوی 5 بیت اطلاعات باشد، باید 32 حرف را روی بلیط های جداگانه بنویسید، همه این بلیت ها را در یک کوزه قرار دهید و سپس یکی را بیرون بیاورید. هر بار که نامه دراز را یادداشت می کنیم و بلیط را به سطل زباله برمی گردانیم و دوباره محتویات آن را مخلوط می کنیم. پس از انجام چنین آزمایشی، به عبارتی مانند زیر می رسیم: RYS البته این متن شباهت بسیار کمی با زبان روسی دارد! برای محاسبه دقیق تر اطلاعات موجود در یک حرف از متن روسی، باید احتمالات ظاهر حروف مختلف را بدانید. مقادیر تقریبی فرکانس حروف جداگانه زبان روسی در جدول زیر جمع آوری شده است: حرف نسبی. فرکانس - 0.175o 0.090e، d 0.072a 0.062 و 0.062t 0.053n 0.053s 0.045 حرف نسبی فرکانس 0.040v 0.038l 0.035k 0.028m 0.026d 0.025p 0.023u 0.021 حرف نسبی فرکانس 0.018y 0.016z 0.016b، b 0.014b 0.014g 0.013h 0.012y 0.010 حرف نسبی فرکانس‌ها 0.009zh 0.007yu 0.006sh 0.006ts 0.004sh 0.003e 0.003f 0.002 از مقایسه این مقدار با مقدار Н0 = log 32 = 5 بیت، می توان دریافت که ظاهر ناهموار حروف مختلف الفبا منجر به کاهش اطلاعات موجود در یک حرف از متن روسی در حدود 0.65 بیت می شود. . کاهش تعداد سیگنال های اولیه مورد نیاز را می توان با کدگذاری حروف جداگانه الفبای روسی با استفاده از روش شانون-فانو نشان داد: کد الفبا. کد حرف تعیین کننده کد حرف تعیین کننده obozn.111k01000h0000100a1010l01001ts00000010b000101m00111ch000011v01010n0111sh00000011g000100o110sch00000001d001101p001100y001000e، o1011r01011،00111t1000yu00000010i1001جدول 8 میانگین تعداد تراشه در این روش از برنامه نویسی یکسان است، پس از آن وجود خواهد داشت بسیار نزدیک به ارزش در تعیین آزمایش آنتروپی برای تعیین یک نامه متن روسی بود، ما در نظر گرفته تمام حروف مستقل . این بدان معنی است که برای نوشتن یک "متن" که در آن هر حرف حاوی کمی اطلاعات باشد، باید از یک کوزه استفاده کنیم که در آن 1000 تکه کاغذ با دقت مخلوط شده است که در 175 مورد آن چیزی نوشته نشده است. ، 90 - حرف o نوشته شده است، 72 - حرف e، ...، در نهایت، روی 2 تکه کاغذ - حرف f (نگاه کنید به جدول 7). با استخراج تکه تکه‌های کاغذ از چنین کوزه‌ای، به «عبارتی» مانند زیر می‌رسیم: YYNT TSIYAA OERV ODNG YUEMLOLIK ZBYA ENVTSHA. این «عبارت» تا حدودی شبیه به یک گفتار پرمعنای روسی نسبت به عبارت قبلی است، اما البته هنوز با یک متن معقول فاصله دارد. عدم تشابه عبارت ما با یک متن معنادار طبیعتاً با این واقعیت توضیح داده می شود که در واقع حروف متوالی متن روسی اصلاً مستقل از یکدیگر نیستند. بنابراین، به عنوان مثال، اگر می دانیم که یک حرف صدادار حرف بعدی است، احتمال ظاهر شدن یک حرف صامت در جای بعدی به طور قابل توجهی افزایش می یابد. حرف "ь" به هیچ وجه نمی تواند از فاصله یا مصوت پیروی کند. حروف "s"، "I" یا "u" نمی توانند پشت حرف "h" ظاهر شوند، اما به احتمال زیاد یکی از مصوت های "and" و "e" یا همخوان "t" و غیره وجود خواهد داشت. روسی زبان قوانین اضافی که در "عبارت" ما در نظر گرفته نشده است منجر به کاهش بیشتر درجه عدم اطمینان یک حرف از متن روسی می شود. برای انجام این کار، فقط لازم است آنتروپی مشروط آزمایش شامل تعیین یک حرف از متن روسی محاسبه شود، مشروط بر اینکه نتیجه آزمایش را بدانیم که شامل تعیین حرف قبلی همان متن است. آنتروپی شرطی با فرمول زیر تعیین می شود: که در آن p (-)، p (a)، p (b)، ...، p (i) احتمال (فرکانس) حروف جداگانه زبان روسی را نشان می دهد. البته از قبل می توان گفت که احتمالات p (--)، p (nb) و بسیاری دیگر (مثلاً p (bb)، p (- b)، p (hw) و غیره) خواهند بود. برابر با صفر می توان مطمئن بود که آنتروپی مشروط کمتر از آنتروپی غیرشرطی خواهد بود. مقدار را می توان به عنوان "اطلاعات متوسط" موجود در تعیین نتیجه تجربه بعدی مشخص کرد. 32 کوزه وجود دارد که با 32 حرف الفبای روسی مشخص شده است. هر یک از کوزه ها حاوی تکه های کاغذی است که ترکیبات دو حرفی روی آن نوشته شده است که با حرف مشخص شده روی کوزه شروع می شود و تعداد تکه های کاغذ با جفت حروف مختلف متناسب با فراوانی (احتمالات) دو حرف مربوطه است. -ترکیب حروف این تجربه شامل برداشتن مکرر تکه‌های کاغذ از کوزه‌ها و نوشتن حرف آخر از روی آنهاست. در این حالت، هر بار (از دومی شروع می شود)، یک تکه کاغذ از کوزه برداشته می شود که حاوی ترکیباتی است که با آخرین حرف نوشته شده شروع می شود. پس از نوشتن نامه، تکه کاغذ به قوطی برگردانده می شود که محتویات آن دوباره کاملاً مخلوط می شود. تجربه از این نوع منجر به یک "عبارت" مانند زیر می شود: UMARONO KACH درج شده توسط DEW NYKH CARPET NEDARE. صدای این "عبارت" به زبان روسی بسیار نزدیکتر است. آگاهی از دو حرف قبل، عدم قطعیت آزمایش شامل تعیین حرف بعدی را کاهش می دهد، که در مثبت بودن تفاوت منعکس می شود، جایی که "آنتروپی شرطی مرتبه دوم" است: هر کدام شامل تکه های کاغذی است که شروع می شود. با همان دو حرف (یا آزمایشی با یک کتاب روسی، که در آن اولین تکرار آخرین ترکیب دو حرفی قبلاً نوشته شده بارها به طور تصادفی یافت می شود و حرف بعدی آن نوشته می شود) منجر به یک "عبارت" می شود مانند موارد زیر: در حالی که عرق راک نورموس به تدریج دانش شما را از بین برد، حتی از سخنرانی قبلی به سخنرانی روسی نزدیکتر بود. به همین ترتیب، تعیین آنتروپی متناظر با تجربه تعیین حرف متن روسی امکان پذیر است، مشروط بر اینکه سه حرف قبلی مشخص باشد. این شامل استخراج تکه‌های کاغذ از 323 کوزه با ترکیب‌های چهار حرفی (یا - آزمایشی مشابه آزمایشی که در بالا با یک کتاب روسی توصیف شده است)، به یک "عبارت" مانند زیر منجر می‌شود: FUN TO GATE NOT DRY AND NEPO و CORKO، یک تقریب حتی بهتر برای آنتروپی یک متن روسی معنی دار، مقادیر N = 5.6، ... است. به راحتی می توان فهمید که با افزایش N، آنتروپی HN فقط می تواند کاهش یابد. اگر ما همچنین در نظر بگیریم که همه مقادیر HN مثبت هستند، می توان از این نتیجه استنباط کرد که مقدار at به یک حد معین تمایل دارد. ما قبلاً می دانیم که میانگین تعداد سیگنال های اولیه مورد نیاز برای انتقال یک حرف از متن روسی نمی تواند کمتر باشد. تفاوتی که نشان می دهد نسبت "آنتروپی محدود کننده" به مقدار مشخص کننده چقدر کمتر از واحد است. بیشترین اطلاعات، که می تواند در یک حرف الفبا با تعداد معینی از حروف باشد، شانون آن را افزونگی زبان نامید. افزونگی زبان روسی (و همچنین افزونگی سایر زبان های اروپایی) به طور قابل توجهی بیش از 50٪ است. یعنی می‌توان گفت که انتخاب حرف بعدی یک متن معنادار بیش از 50 درصد توسط ساختار خود زبان تعیین می‌شود و بنابراین، فقط تا حد نسبتاً کمی تصادفی است. افزونگی R یک مشخصه آماری بسیار مهم یک زبان است، اما مقدار عددی آن هنوز با دقت رضایت بخشی برای هیچ زبانی تعیین نشده است. در رابطه با زبان روسی، به ویژه، فقط داده هایی در مورد مقادیر مقادیر H2 و H3 وجود دارد. Н0Н1Н2Н3log 32 = 54.353.523.01 (برای کامل بودن، در اینجا مقادیر آنتروپی Н0 و Н1 را نیز آورده ایم). از این فقط می توان استنباط کرد که برای زبان روسی، در واقع، مقدار R بسیار بیشتر از این عدد است. واضح است که برای همه زبان های استفاده می شود الفبای لاتین، حداکثر اطلاعات Н0 که می تواند روی یک حرف از متن بیفتد، به همین معنی است: بیت (26 حرف مختلف الفبا و 27 "حرف" فضای خالی بین کلمات است). با استفاده از جداول بسامدهای نسبی حروف مختلف در انگلیسی، آلمانی، فرانسوی و اسپانیایی، می توان نشان داد که آنتروپی H1 برای این زبان ها برابر است (به بیت): زبان آلمانی فرانسوی فرانسوی اسپانیایی Н14,034,103,963,98 می بینیم که در همه موارد، مقدار H1 به طور قابل توجهی کمتر از H0 = log 27 4.76 بیت است و مقادیر آن برای زبانهای مختلفتفاوت زیادی با یکدیگر ندارند مقادیر H2 و H3 برای زبان انگلیسی توسط شانون محاسبه شد، در حالی که او از جداول فراوانی موجود در انگلیسی برای ترکیب‌های مختلف دو حرفی و سه حرفی استفاده کرد. با در نظر گرفتن آمار فراوانی وقوع کلمات مختلفدر زبان انگلیسی، شانون توانست مقادیر H5 و H8 را تقریباً تخمین بزند. در نتیجه، او دریافت کرد: Н0Н1 Н2Н3Н5Н84.764.03 3.323.10≈2.1≈1.9 از این می توان نتیجه گرفت که برای زبان انگلیسی افزونگی R در هر صورت کمتر از 60 درصد نیست، یعنی از 60% تجاوز کند. شمارش مقادیر H9، H10 و غیره طبق فرمول شناخته شده برای ما غیرممکن است، زیرا محاسبه H9 نیاز به آگاهی از احتمالات همه ترکیبات 9 حرفی دارد که تعداد آنها با یک 13 رقم بیان می شود. عدد (تریلیون ها!). بنابراین، برای تخمین مقادیر HN در مقادیر بزرگ N باید محدود شود روش های غیر مستقیم... اجازه دهید در مورد یکی از این نوع روش پیشنهاد شده توسط شانون صحبت کنیم. "آنتروپی مشروط" НN اندازه گیری درجه عدم قطعیت تجربه است که شامل تعیین می شود حرف Nمتن، مشروط بر اینکه حروف N - 1 قبلی برای ما شناخته شده باشد. آزمایشی برای حدس زدن حرف N به راحتی قابل تنظیم است: برای این کار کافی است یک قطعه (N - 1) -alphate از یک متن معنی دار انتخاب کنید و کسی را دعوت کنید تا حرف بعدی را حدس بزند. چنین آزمایشی را می توان بارها تکرار کرد و دشواری حدس زدن حرف N را می توان با استفاده از مقدار متوسط QN تعداد تلاش های لازم برای یافتن پاسخ صحیح تخمین زد. واضح است که مقادیر QN تعریف شده برای معانی مختلف N، ویژگی های خاصی از ساختار آماری زبان، به ویژه، افزونگی آن است. شانون یک سری آزمایش مشابه انجام داد که در آن N مقادیر 1، 2، 3، ...، 14، 15 و 100 را به خود اختصاص داد. با انجام این کار، او متوجه شد که حدس زدن حرف 100 توسط 99 حرف قبلی یک کار بسیار ساده تر از حدس زدن حرف 15 در 14 قبلی است. از این رو، می توانیم نتیجه بگیریم که H15 به طور قابل توجهی بزرگتر از H100 است، یعنی هنوز نمی توان H15 را با مقدار محدود کننده شناسایی کرد. متعاقباً، همان آزمایش‌ها روی ماده کمی بزرگتر برای N = 1، 2، 4، 8، 16، 32، 64، 128 و N ≈ 10000 انجام شد. Н16 حتی به طور قابل توجهی بزرگتر از این مقدار است. بنابراین، می توان فرض کرد که با افزایش N، مقدار HN تا مقادیر N = 30 کاهش می یابد، اما با افزایش بیشتر در N، عملا تغییر نمی کند. بنابراین، به جای "آنتروپی محدود" می توان به عنوان مثال، از آنتروپی شرطی H30 یا H40 صحبت کرد. آزمایشات روی حدس زدن حروف نه تنها به ما امکان قضاوت می دهد ارزش نسبیآنتروپی های مشروط HN برای N مختلف، اما همچنین محاصره مقادیر خود HN را ممکن می کند. با توجه به داده‌های چنین آزمایش‌هایی، نه تنها می‌توان میانگین تعداد تلاش‌های QN مورد نیاز برای حدس زدن حرف N متن را با N - 1 قبلی، بلکه احتمال (فرکانس) صحیح بودن حرف را نیز تعیین کرد. از 1، 2، 3، ...، n ام تلاش حدس زده می شود (که در آن n = 27 تعداد حروف الفبا است؛ QN =). به راحتی می توان فهمید که احتمالات برابر با احتمالات حروف الفبا است که به ترتیب نزولی مرتب شده اند. در واقع، اگر هیچ یک از حروف قبل از حرف x را برای حدس ندانیم، طبیعی است که اول از همه فرض کنیم که x با رایج ترین حرف a1 منطبق است (و احتمال حدس زدن درست در اینجا برابر با p خواهد بود. (a1))؛ پس باید فرض کرد که x منطبق بر a2 است (احتمال پاسخ صحیح در اینجا برابر با p (a2) خواهد بود) و به همین ترتیب. از این رو آنتروپی H1 برابر با مجموع است. اگر N> 1 باشد، می توان نشان داد که مجموع (*) از آنتروپی مشروط HN تجاوز نمی کند (این به دلیل این واقعیت است که مقادیر به روش خاصی میانگین احتمالات نتایج آزمایش را نشان می دهند) . از سوی دیگر، ملاحظات تا حدودی پیچیده‌تر، که در اینجا به آنها نمی‌پردازیم، به ما اجازه می‌دهد ثابت کنیم که مجموع (**) برای هر N بزرگتر از آنتروپی مشروط НN نخواهد بود. بنابراین، عبارات (*) و (**) (متشکل از احتمالاتی که می توان از داده های تجربی تخمین زد) مرزهایی را تعیین می کند که مقدار HN باید بین آنها قرار گیرد. فقط باید در نظر داشته باشید که هر دو تخمین (*) و (**) با این فرض به دست می آیند که اینها احتمالات حدس زدن یک حرف از N - 1 حرف قبلی از تلاش های اول، دوم، سوم و غیره است. با این فرض به دست می آیند که حدس دهنده همیشه حرف بعدی را به مصلحت ترین نام می برد - با در نظر گرفتن کامل همه قوانین آماری از این زبان... در شرایطی که تجربیات واقعیهرگونه اشتباه در استراتژی فرد حدس‌زن (یعنی تفاوت حروفی که او می‌خواند و حروفی که باید بر اساس آمار دقیق زبان نامگذاری شوند) به ناچار منجر به تخمین بیش از حد مجموع (*) و () می‌شود. **)؛ به همین دلیل است که توصیه می شود فقط داده های "موفق ترین حدس زن" را در نظر بگیرید، زیرا برای او این تخمین بیش از حد کوچکترین خواهد بود. از آنجایی که هر فرد حدس‌زن گاهی اوقات اشتباه می‌کند، تخمین (**) در عمل نمی‌تواند یک تخمین کاملاً قابل اعتماد کمتر از آنتروپی واقعی در نظر گرفته شود (برخلاف تخمین بالایی (*)، که به دلیل خطاهای حدس‌زن، فقط می‌تواند تبدیل شود. حتی بزرگتر). علاوه بر این، مقادیر مجموع (*) و (**)، متأسفانه، با افزایش N به طور نامحدود نزدیک نمی شوند (با شروع از N ≈ 30، این مجموع به طور کلی به N بستگی ندارند). بنابراین، تخمین‌های افزونگی زبان به‌دست‌آمده در این مسیر چندان دقیق نخواهد بود. به طور خاص، آزمایش‌های شانون فقط نشان داد که مقدار H100 بین 0.6 تا 1.3 بیت به نظر می‌رسد. از این رو، می توان نتیجه گرفت که افزونگی برای زبان انگلیسی به ترتیب بزرگی باید نزدیک به 80٪ باشد. 2.2.2 گفتار شفاهی. اکنون به مسئله آنتروپی و اطلاعات در گفتار شفاهی می پردازیم. طبیعی است که فکر کنیم تمام ویژگی های آماری چنین سخنرانی حتی بیشتر به انتخاب افرادی که صحبت می کنند و به ماهیت گفتگوی آنها بستگی دارد. کاهش ارزش آنتروپی گفتار شفاهی ممکن است به این دلیل باشد که در یک مکالمه اغلب از تکرارهای بیشتر همان کلمات استفاده می کنیم و اغلب کلمات "اضافی" زیادی اضافه می کنیم - این کار هم برای تسهیل درک گفتار انجام می شود. و به سادگی به این ترتیب که گوینده وقت داشته باشد تا آنچه را که می‌خواهد بعداً بگوید در نظر بگیرد. با تعیین میانگین تعداد حروف تلفظ شده در واحد زمان، می توان به طور تقریبی مقدار اطلاعات ارسال شده در طول مکالمه را در 1 ثانیه تخمین زد. معمولاً بین 5 تا 6 بیت است. از گفت و گو می توان در مورد روحیه گوینده و نگرش او به آنچه گفته شد قضاوت کرد. ما می توانیم گوینده را بشناسیم، حتی اگر هیچ منبع اطلاعاتی دیگری او را به ما نشان ندهد. ما در بسیاری از موارد می توانیم محل تولد یک غریبه را با تلفظ او تعیین کنیم. ما می توانیم بلندی گفتار شفاهی را تخمین بزنیم، که در مورد انتقال صدا از طریق یک خط ارتباطی تا حد زیادی به طور خالص تعیین می شود. مشخصات فنیخطوط انتقال و غیره. کمی کردن همه این اطلاعات یک کار بسیار دشوار است که به دانش بسیار بیشتری از زبان نیاز دارد. یک استثنا در این زمینه، مسئله نسبتاً محدود استرس های منطقی است که بر کلمات فردی در یک عبارت تأکید می کند. استرس اغلب روی کلماتی است که به ندرت استفاده می شود (که البته کاملاً طبیعی است - واضح است که به ندرت کسی با یک استرس منطقی بر رایج ترین فیل تأکید می کند - مثلاً حروف اضافه یا حروف ربط). اگر این احتمال وجود دارد که کلمه داده شده Wr تحت تنش است، آن را با qr نشان می دهیم، سپس میانگین اطلاعات شامل اطلاعات مربوط به وجود یا عدم وجود استرس در این کلمه برابر خواهد شد.حالا فرض کنید احتمالات (فرکانس) همه کلمات W1، W2، باشد. ... ., WK (اینجا K - تعداد کلهمه کلمات استفاده شده در این مورد، برای اطلاعات متوسط H، محصور در یک تنش منطقی، می‌توانید فرمول زیر را بنویسید: میانگین اطلاعاتی که با فهمیدن اینکه استرس منطقی روی کدام کلمات قرار می‌گیرد به‌دست می‌آوریم به ترتیب بزرگی به 0.65 بیت در کلمه نزدیک است. . در طول مکالمه، حروف تکی هرگز تلفظ نمی شوند، اما صداهایی تلفظ می شوند که تفاوت قابل توجهی با حروف دارند. بنابراین، عنصر اصلی گفتار شفاهی باید یک صدای جداگانه در نظر گرفته شود - یک واج. زبان گفتاری معنادار از واج ها تشکیل شده است، همان طور که زبان نوشتاری معنادار از حروف ساخته شده است. بنابراین در تمام مواردی که فقط به انتقال «اطلاعات معنایی» گفتار شفاهی علاقه داریم بیشترین علاقهآنتروپی و اطلاعات یک "حرف گفتاری" را نشان نمی دهد، بلکه آنتروپی و اطلاعات یک واج واقعی را نشان می دهد. فهرست واج های یک زبان، البته، با فهرست حروف الفبا منطبق نیست، زیرا همان حرف در موارد مختلفممکن است متفاوت به نظر برسد 42 واج مختلف در زبان روسی وجود دارد و بسامدهای تک تک واج ها را شمارش کرده اند (و همچنین ترکیبات مختلفدو و سه واج متوالی). Н0 = log 42 یک واج، آنتروپی مرتبه اول (که در آن بسامدهای نسبی واج های مختلف وجود دارد) و "آنتروپی شرطی" Н2 و Н3: Н0Н1Н2Н3log 42 ≈ 5.38 4.77 3.62 0.70 اگر این مقادیر را با هم مقایسه کنیم. از Н0، Н1، Н2، H3 برای گفتار نوشتاری روسی، سپس کاهش تعداد آنتروپی شرطی برای واج ها به طور قابل توجهی سریعتر از حروف متن نوشته شده رخ می دهد. برای تعیین افزونگی R (کلمات)، می توانید رابطه ای بین افزونگی گفتار و نوشتار برقرار کنید. از این واقعیت که گفتار شفاهی را می توان ضبط و نوشت - خواند، نتیجه می شود که "اطلاعات کامل" موجود در یک متن خاص به شکلی که در آن - شفاهی یا کتبی - این متن ارائه شده است بستگی ندارد، یعنی اینکه . .. از این رو نتیجه می شود که میانگین تعداد حروف در هر واج کجاست ("طول واج متوسط"). این مقدار یک مشخصه آماری مهم زبان است که گفتار و نوشتار را به هم پیوند می دهد. همچنین از آخرین فرمول چنین استنباط می شود که k تعداد کل واج ها و n تعداد حروف است. زیرا در اینجا طبیعی تر است که بگیریم. با این حال، استفاده از این فرمول به دلیل فقدان داده های آماری برای تعیین مقدار با مشکل مواجه می شود. 2.2.3 موسیقی. از همین دست می توان در مورد پیام های موسیقی نیز تحقیق کرد. طبیعی است که فکر کنیم ارتباط بین صداهای متوالی یک ملودی خاص، که با نشانه های نت فردی بیان می شود، به اندازه کافی قوی است: از آنجایی که برخی از ترکیبات صداها هماهنگ تر از سایرین خواهند بود، اولی بیشتر در آثار موسیقی یافت می شود. دومی. اگر مجموعه ای از یادداشت ها را به صورت تصادفی بنویسیم، اطلاعات موجود در هر یادداشت این رکورد بزرگترین خواهد بود. با این حال، از نقطه نظر موسیقی، چنین توالی هرج و مرج از نت ها ارزشی نخواهد داشت. برای به دست آوردن صدایی دلپذیر، لازم است که افزونگی خاصی را در محدوده خود وارد کنیم. در عین حال، می توان ترسید که در مورد افزونگی بیش از حد، که در آن نت های بعدی تقریباً بدون ابهام توسط نت های قبلی تعیین می شوند، فقط موسیقی بسیار یکنواخت و غیر جالب دریافت خواهیم کرد. افزونگی که در آن می توان موسیقی "خوب" به دست آورد چیست؟ افزونگی ملودی های سادهچیزی کمتر از زائد بودن گفتار معنادار نیست. لازم است به طور خاص مسئله افزونگی اشکال مختلف مطالعه شود آثار موسیقییا آثاری از آهنگسازان مختلف. به عنوان مثال، یک آلبوم محبوب از آهنگ های کودکان را از دیدگاه تئوری اطلاعات تجزیه و تحلیل کنید. برای سادگی، این اثر فرض کرده است که همه صداها در یک اکتاو هستند. از آنجایی که به اصطلاح کروماتیسم در ملودی های مورد بررسی وجود نداشت، همه این ملودی ها را می توان به هفت صدای اصلی تقلیل داد. دو، ری، می، فا، سل، لا و سی، هر کدام یک هشتم در مدت زمان. محاسبه اصوات با مدت زمان بیش از یک هشتم با افزودن هشتمین "عنصر اصلی" O به هفت نت انجام شد که نشان دهنده تمدید صدای قبلی برای مدت زمان دیگری از یک هشتم (یا مکثی از یک هشتم) است. یک هشتم). بنابراین، "حداکثر آنتروپی ممکن" H0 یک نت در اینجا برابر با H0 = log 8 = 3 بیت است. با محاسبه فرکانس (احتمالات) نت های فردی در تمام 39 آهنگ تجزیه و تحلیل شده، متوجه می شویم که با استفاده از احتمالات یافت شده از ترکیب دو نت، می توانیم آنتروپی شرطی H2 را نیز محاسبه کنیم، معلوم می شود که نزدیک به 2.42 است. از مقادیر H1 و H2 به تنهایی، در مورد میزان افزونگی موارد در نظر گرفته شده بسیار کمی می توان گفت، ظاهراً به طور قابل توجهی بالاتر از آن است. این نتیجه گیری توسط تحقیقات بسیاری از نویسندگان مشهور پشتیبانی می شود. 2.2.4 انتقال تصاویر تلویزیونی... چشم ما قادر است فقط تعداد محدودی از درجات روشنایی یک تصویر را تشخیص دهد و فقط قسمت های نه چندان نزدیک آن را تشخیص دهد، بنابراین هر تصویری را می توان "نقطه به نقطه" منتقل کرد، که هر یک سیگنالی است که فقط یک عدد محدود می گیرد. از ارزش ها لازم است تعداد قابل توجهی (چند ده) درجه بندی درجه سیاه شدن ("روشنی") هر عنصر در نظر گرفته شود، علاوه بر این، در هر ثانیه 25 فریم روی صفحه تلویزیون جایگزین می شود و این تصور "حرکت" را ایجاد می کند. ". با این حال، خط ارتباطی در واقع نتیجه آزمایش را که شامل تعیین مقدار تغییر مداوم از نقطه به نقطه، در زمان و رنگ یا روشنایی تصویر است، منتقل نمی‌کند، بلکه نتیجه آزمایش کاملاً متفاوت است. آزمایش کوانتیزه شده، شامل تعیین رنگ (سفید یا سیاه) یا درجه بندی روشنایی در تعداد محدودی از "نقاط". این تجربه جدید می تواند در حال حاضر فقط تعداد محدودی از نتایج داشته باشد، و ما می توانیم آنتروپی آن را اندازه گیری کنیم. با به اصطلاح "قدرت تفکیک" چشم، یعنی توانایی آن در تشخیص نواحی نزدیک تصویر. در تلویزیون مدرن، این عدد معمولاً در حدود چند صد هزار است (در برنامه های تلویزیونی شوروی، تصویر به 400000 - 500000 عنصر تجزیه می شود، در آمریکایی - حدود 200،000 - 300،000، در برنامه های برخی از مراکز تلویزیونی فرانسه و بلژیک - تقریباً 1,000,000) ... به راحتی می توان فهمید که به همین دلیل آنتروپی یک تصویر تلویزیونی بسیار زیاد است. حتی اگر فرض کنیم که چشم انسان تنها 16 درجه مختلف روشنایی را متمایز می کند (مقدار به وضوح دست کم گرفته می شود) و تصویر تنها به 200000 عنصر تجزیه می شود، در می یابیم که "آنتروپی مرتبه صفر" در اینجا برابر با Н0 = است. log 16,200,000 = 800,000 بیت. مقدار آنتروپی واقعی H، البته، کمتر خواهد بود، زیرا تصویر تلویزیون دارای افزونگی قابل توجهی است. هنگام محاسبه مقدار H0، ما فرض کردیم که مقادیر روشنایی در هر دو نقطه از تصویر مستقل از یکدیگر هستند، در حالی که در واقع، روشنایی معمولاً هنگام رفتن به عناصر همسایهتصویر یکسان (یا حتی متفاوت، اما نزدیک به زمان). معنای بصری این افزونگی R این است که از میان 16200000 ترکیب ممکن از مقادیر روشنایی ما در تمام نقاط صفحه، ترکیب‌های معنی‌داری که می‌توان آنها را "تصاویر" نامید تنها بخش ناچیزی را تشکیل می‌دهد و بقیه کاملاً بی‌نظم خواهند بود. مجموعه ای از نقاط با روشنایی های مختلف بسیار دور از هر "نقشه". در همین حال، "درجه عدم قطعیت" واقعی H تصویر تلویزیون باید تنها ترکیبی از مقادیر روشنایی را در نظر بگیرد که حداقل شانسی برای انتقال دارند. برای تعیین مقدار دقیق آنتروپی H (یا افزونگی R) یک تصویر تلویزیونی، لازم است روابط آماری بین روشنایی نقاط مختلف صفحه را به طور دقیق مطالعه کنیم. بنابراین، مقادیر آنتروپی‌های H0، H1، H2 و H3 برای دو تصویر تلویزیونی خاص پیدا شد که اولی (تصویر A - پارکی با درختان و ساختمان‌ها) پیچیده‌تر بود و دومی (تصویر B - یک گالری نسبتاً تاریک با رهگذران) از نظر رنگی تک رنگ‌تر بود و حاوی جزئیات کمتری بود، در حالی که 64 درجه متفاوت از روشنایی یک عنصر از یک تصویر تلویزیونی را متمایز می‌کرد، بنابراین آنتروپی H0 (به یک عنصر اشاره دارد و نه به کل تصویر. به طور کلی) در اینجا برابر با H0 = log 64 = 6 بیت است. سپس با استفاده از یک دستگاه رادیویی خاص، فرکانس‌های نسبی (احتمالات) همه درجه‌بندی‌های روشنایی قابل تشخیص برای هر دو تصویر مورد بررسی محاسبه شد و "آنتروپی مرتبه اول" که عنصر اول دارای مقدار روشنایی است، تعیین شد. j-e دومو همچنین فرکانس های نسبی pijk از سه عنصر همسایه (همچنین فقط به صورت افقی) که در آن عنصر اول مقدار روشنایی i-e، j-e دوم و سومین کیلو(اعداد i، j و k در تمام مقادیر از 1 تا 64 عبور کردند). این فرکانس ها امکان تعیین "آنتروپی آزمایش های پیچیده" و سپس "آنتروپی های مشروط" و آخرین موردی که در آن فقط برای تصویر B محاسبه شد را ممکن ساخت. نتایج به دست آمده در جدول زیر خلاصه شده است: , 91.5 افزونگی R، تخمین زده شده توسط مقدار H2 برای تصویر A 44٪ و برای تصویر B - 68٪ است. ارزش واقعیفقط می تواند بیش از این افزونگی وجود داشته باشد. در مورد آنتروپی شرطی H3 برای روشنایی شناخته شده دو عنصر قبلی یک خط، تفاوت نسبتا کمی با H2 دارد (تصویر B، 75٪). از این می‌توان نتیجه گرفت که آگاهی از روشنایی نزدیک‌ترین عنصر، بخش بسیار بزرگی از افزونگی کل را تعیین می‌کند. تجربه دیگری که بر تقسیم بندی تکیه دارد نیز شخصیتی مشابه دارد. مقادیر ممکنروشنایی یک عنصر تصویر تلویزیونی با 8 درجه، نه 64 درجه، که برای آن آنتروپی های H0 و H1 و تعدادی از آنتروپی های شرطی H2، H3 و H4 یک عنصر تصویر برای چهار نمودار تلویزیونی ورزشی زیر محاسبه می شود: A - دویدن سریع بسکتبالیست ها، ب - چهره یک تماشاگر از نمای نزدیک روی جایگاه استادیوم، ج - پانینگ از دید تماشاگران روی جایگاه و د - بازیکنان فوتبال با سرعت دویدن. با اعداد 1 و 2 عناصر تصویر مجاور داده ها را به صورت افقی و عمودی، با عدد 3 - عنصر مجاور مورب، با عدد 4 - همان مورد در نظر گرفته شده، عنصر را در قاب قبلی نشان می دهیم. پخش تلویزیونی، با شماره 5 - عنصر در همان افقی، در مجاورت عنصر 1، و، در نهایت، شماره 6 - همان عنصر در قاب قبل از آن که حاوی عنصر 4 (شکل 1)، a) b. ) شکل 1. و ما در علامت گذاری آنتروپی های شرطی از بالا در پرانتز تعداد تصاویر عناصر را نشان خواهیم داد که درجه روشنایی آنها مشخص است. در این مورد، مقادیر آنتروپی (در بیت) را می توان در جدول زیر خلاصه کرد: A31,960,690,98-1,77B31,950,360.36 - B32,781,341,952.78-G32.45-2.002.08-2.002.08 A0 , 56 - B0.35-0.270.26-B - 1.221.181.19G-1.83 --- نتایج آخرین آزمایش منجر به این نتیجه می شود که برای تصویر ضعیف در جزئیات ("چهره") افزونگی کمتر از 90٪، و برای یک تصویر غنی از جزئیات ("بینندگان")، کمتر از 60٪ نیست. دلایل این اختلاف هنوز مشخص نیست. برای تصاویر تلویزیونی رنگی، اطلاعات به ترتیب بزرگی قابل مقایسه با اطلاعات دو برابر شده موجود در تصویر سیاه و سفید مربوطه است. نتیجه گیری در این کار، اهداف و مقاصد زیر تعیین شد. هدف: بررسی اصول کدگذاری اطلاعات شانون - فانو و هافمن و کاربرد آنها در حل مسائل. هدف: مطالعه آنتروپی و افزونگی انواع خاصی از پیام ها برای کاربرد بعدی اصول شانون - فانو و هافمن برای آنها. پس از تکمیل اهداف و مقاصد پایان نامهنتیجه گیری های زیر انجام شد. قبل از ظهور آثار شانون و فانو، رمزگذاری کاراکترهای الفبا هنگام انتقال پیام از طریق کانال های ارتباطی با همان تعداد بیت انجام می شد که با فرمول هارتلی به دست می آمد. با ظهور این آثار، روش هایی به وجود آمد که کاراکترها را با تعداد بیت های متفاوت، بسته به احتمال ظاهر شدن آنها در متن، رمزگذاری می کنند، یعنی کاراکترهای محتمل تر با کدهای کوتاه و کاراکترهای نادر با کدهای رمزگذاری می شوند. طولانی (بیشتر از حد متوسط). از زمانی که دی.ای. مقدار زیادیتحقیقات بیشتر در این زمینه شایان ذکر است که بیش از 50 سال از تاریخ انتشار، کد هافمن ارتباط و اهمیت خود را به هیچ وجه از دست نداده است. بنابراین می توانیم با اطمینان بگوییم که به هر شکلی با آن روبرو هستیم (واقعیت این است که کد هافمن به ندرت به طور جداگانه استفاده می شود، اغلب در ارتباط با الگوریتم های دیگر کار می کند)، تقریباً هر بار که فایل ها را بایگانی می کنیم، عکس ها را تماشا می کنیم. ، فیلم، ارسال فکس یا گوش دادن به موسیقی. از مزایای این روش ها می توان به سهولت آشکار اجرای آنها و در نتیجه، سرعت بالارمزگذاری و رمزگشایی عیب اصلی این است که در حالت کلی بهینه نیستند. 3
الگوریتم محاسبه کدهای شانون-فانو را در نظر بگیرید (برای وضوح، بیایید دنباله "aa bbb cccc ddddd" را به عنوان مثال در نظر بگیریم). برای محاسبه کدها، باید جدولی از نمادهای پیام منحصر به فرد ایجاد کنید ج (من)و احتمالات آنها p (c (i))، و آن را به ترتیب غیر افزایشی احتمال نماد مرتب کنید.
| ج (من) | p (c (i)) |
| د | 5 / 17 |
| ج | 4 / 17 |
| فضا | 3 / 17 |
| ب | 3 / 17 |
| آ | 2 / 17 |
علاوه بر این، جدول نمادها به دو گروه تقسیم می شود به طوری که هر یک از گروه ها در مجموع نمادها تقریباً فرکانس یکسانی دارند. گروه اول روی ابتدای کد "0" و گروه دوم در "1" تنظیم شده است. برای محاسبه بیت های بعدی کدهای کاراکتر، این روش به صورت بازگشتی برای هر گروهی که بیش از یک کاراکتر دارد تکرار می شود. بنابراین، برای مورد ما، کدهای کاراکتر زیر را دریافت می کنیم:
طول کد s (i)در جدول به دست آمده است int (-lg p (c (i)))، اگر می شد سیول ها را به گروه هایی با همان فرکانسدر غیر این صورت، طول کد است int (-lg p (c (i))) + 1.
طول 39 بیت با توجه به اینکه نسخه اصلی 136 بیت بود، نسبت فشرده سازی ~ 28٪ را دریافت می کنیم - نه چندان بد.
با نگاهی به دنباله حاصل، این سوال مطرح می شود: "چگونه می توانید اکنون این را از حالت فشرده خارج کنید؟" ما نمی توانیم مانند مورد رمزگذاری، هر 8 بیت جریان ورودی را با یک کد با طول متغیر جایگزین کنیم. هنگام فشرده سازی، باید برعکس عمل کنیم - کد با طول متغیر را با یک کاراکتر 8 بیتی جایگزین کنیم. V در این مورد، بهتر است از یک درخت دوتایی استفاده کنید که برگ های آن نماد هستند (مشابه درخت هافمن).
کدگذاری شانون-فانو یک روش فشرده سازی نسبتاً قدیمی است و امروزه از اهمیت عملی خاصی برخوردار نیست (به جز به عنوان تمرینی در دوره ساختارهای داده). در اغلب موارد، طول دنباله فشرده، طبق این روش، با طول دنباله فشرده با استفاده از کدگذاری هافمن برابر است. اما در برخی از توالی‌ها، کدهای شانون-فانو غیربهینه هنوز تشکیل می‌شوند، بنابراین فشرده‌سازی با روش هافمن کارآمدتر در نظر گرفته می‌شود. به عنوان مثال، دنباله ای با محتوای کاراکتر زیر در نظر بگیرید: "a" - 14، "b" - 7، "c" - 5، "d" - 5، "e" - 4. روش هافمن آن را به 77 بیت فشرده می کند. ، اما Shannon-Fano تا 79 بیت.
|
چگونه به گروه ها تقسیم شدیم؟ به اندازه کافی ساده:
به دلیل این ابهام، حتی برخی از افراد چنین افکاری دارند: "... برنامه گاهی اوقات به برخی از نمادها اختصاص می دهد ..." و غیره - استدلال در مورد طول کدها. اگر هوش مصنوعی نمی نویسید، پس چیزی مانند "برنامه گاهی اوقات" کاری را انجام می دهد مضحک به نظر می رسد. یک الگوریتم به درستی اجرا شده به شدت کار می کند.
همین پیام را می توان رمزگذاری کرد روش های مختلف... سودمندترین کد کدی است که کمترین زمان را برای انتقال پیام صرف می کند. اگر انتقال هر یک از عناصر کاراکتر (مثلاً 0 یا 1) زمان یکسانی داشته باشد، کد بهینه به گونه ای خواهد بود که هنگام استفاده برای انتقال یک پیام طول داده شدهحداقل تعداد کاراکترهای ابتدایی صرف خواهد شد. شانون - کدهای فانو پیشوند هستند، یعنی. نه کلمه رمزپیشوند دیگری نیست این ملکامکان رمزگشایی بدون ابهام از هر دنباله ای از کلمات رمز را فراهم می کند
اجازه دهید اصل ساخت یکی از اولین الگوریتم های فشرده سازی را که توسط دانشمندان آمریکایی شانون و فانو با استفاده از مثال حروف الفبای روسی فرموله شده است، در نظر بگیریم. الگوریتم از کدهای با طول متغیر استفاده می کند، به عنوان مثال. یک کاراکتر معمولی با یک کد با طول کوتاه تر، یک کاراکتر نادر - یک کد طولانی تر رمزگذاری می شود.
برای نوشتن چنین کدی، بدیهی است که باید فراوانی وقوع حروف در متن روسی را بدانید. این فرکانس ها در جدول 1 نشان داده شده است. حروف در جدول به ترتیب نزولی مرتب شده اند.
میز 1
فراوانی ظاهر حروف الفبای روسی
با استفاده از جدول، می توانید مقرون به صرفه ترین کد را بر اساس ملاحظات مربوط به اطلاعات بنویسید. بدیهی است که زمانی که هر کاراکتر ابتدایی ارسال شود، کد مقرون به صرفه‌تر خواهد بود حداکثر اطلاعات... یک نماد ابتدایی (یعنی نشان دهنده سیگنال آن) را در نظر بگیرید سیستم فیزیکیبا دو حالت ممکن: 0 و 1. اطلاعاتی که این نماد می دهد برابر با آنتروپی این سیستم است و در حالتی حداکثر است که هر دو حالت به یک اندازه محتمل باشند. در این حالت، نماد ابتدایی اطلاعات 1 (دودویی) را منتقل می کند. بنابراین، مبنای کدگذاری بهینه این الزام خواهد بود که کاراکترهای ابتدایی در متن رمزگذاری شده به طور متوسط به همان میزان تکرار شوند.
ایده کدگذاری این است که کاراکترهای رمزگذاری شده (حروف یا ترکیب حروف) به دو گروه تقریباً مساوی تقسیم می شوند: برای اولین گروه از کاراکترها، اولین مکان ترکیب 0 است (نخستین کاراکتر عدد باینری). نشان دهنده شخصیت)؛ برای گروه دوم - 1. علاوه بر این، هر گروه مجدداً به دو زیر گروه تقریباً مساوی تقسیم می شود. برای نمادهای زیر گروه اول، 0 در وهله دوم قرار می گیرد. برای زیر گروه دوم - یک و غیره.
اجازه دهید اصل ساخت کد شانون-فانو را با استفاده از مثالی از مواد الفبای روسی نشان دهیم (جدول 1 را ببینید). بیایید شش حرف اول را بشماریم (از "-" تا "t")؛ با جمع کردن احتمالات (فرکانس) آنها 0.498 بدست می آید. همه حروف دیگر از "n" تا "f" تقریباً همان احتمال 0.502 را خواهند داشت. شش حرف اول (از "-" تا "t") در وهله اول دارای علامت باینری 0 خواهند بود و بقیه حروف (از "n" تا "f") در وهله اول دارای 1 خواهند بود. علاوه بر این، ما دوباره گروه اول را به دو زیر گروه تقریباً مساوی تقسیم می کنیم: از "-" تا "o" و از "e" تا "t". برای تمام حروف زیرگروه اول در وهله دوم صفر و زیرگروه دوم - یک قرار می دهیم. ما این روند را تا زمانی ادامه می دهیم که در هر زیربخش دقیقاً یک حرف وجود داشته باشد که در قسمت خاصی کدگذاری می شود عدد باینری... مکانیسم ساخت در جدول 2 و خود کد در جدول 3 نشان داده شده است.
جدول 2
مکانیسم ساخت کد شانون - فانو بر روی نمونه الفبای روسی
| علائم باینری | |||||||||
| نامه ها | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | |||||||||
| O | |||||||||
| ه | |||||||||
| آ | |||||||||
| و | |||||||||
| تی | |||||||||
| n | |||||||||
| با | |||||||||
| آر | |||||||||
| v | |||||||||
| ل | |||||||||
| به | |||||||||
| متر | |||||||||
| د | |||||||||
| پ | |||||||||
| در | |||||||||
| من هستم | |||||||||
| س | |||||||||
| س | |||||||||
| ب، ب | |||||||||
| ب | |||||||||
| جی | |||||||||
| ساعت | |||||||||
| هفتم | |||||||||
| ایکس | |||||||||
| f | |||||||||
| یو | |||||||||
| w | |||||||||
| ج | |||||||||
| SCH | |||||||||
| هه | |||||||||
| f |
جدول 3
نتیجه رمزگذاری حروف الفبای روسی با کد شانون - فانو
مثال 4.بیایید عبارت "روش رمزگذاری" را با استفاده از کد شانون - فانو بنویسیم.
راه حل:بیایید از جدول 3 استفاده کنیم و نتیجه زیر را بدست آوریم:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) فضا
(10111) تا (001) o (110010) d (0110) و (10100) r (001) o (10101) c
(0101) a (1000) n (0110) و (110110) i
توجه داشته باشید که نیازی به جدا کردن حروف از یکدیگر با یک کاراکتر خاص نیست، زیرا حتی بدون این رمزگشایی به دلیل خاصیت پیشوند بدون ابهام انجام می شود: هیچ کلمه رمز کوتاهتر شروع یک کلمه رمز طولانی تر نیست. در واقع، جدول 3 نشان می دهد که کوتاه ترین کدها برای کاراکترهای "space" و "o" هستند. علاوه بر این، نه یکی دیگر کد طولانی 000 ("فضا") و 001 ("o") در ابتدای دنباله ندارد. همین امر را می توان برای سایر دنباله های باینری کد شانون - فانو مشاهده کرد که در جدول 3 نشان داده شده است.
لازم به ذکر است که هرگونه خطای کدگذاری (اختلاط تصادفی 0 یا 1 کاراکتر) با چنین کدی کشنده است، زیرا رمزگشایی کل متن پس از خطا غیرممکن می شود.
مثال 5.تعیین کنید آیا کدی که در نظر گرفته ایم در صورت عدم وجود خطا بهینه است؟
راه حل:اجازه دهید میانگین اطلاعات در هر نماد ابتدایی (0 یا 1) را پیدا کرده و آن را با حداکثر مقایسه کنیم اطلاعات احتمالی، که برابر با یک است. برای انجام این کار، ابتدا میانگین اطلاعات موجود در یک حرف از متن ارسالی، یعنی آنتروپی در هر حرف را پیدا می کنیم (فرمول 8 را ببینید):
طبق جدول 1، میانگین تعداد نویسه های ابتدایی در هر حرف را تعیین می کنیم:
بنابراین، اطلاعات به ازای هر کاراکتر بسیار نزدیک به حد بالای یک است، و کد داده شدهبسیار نزدیک به بهینه
در مورد استفاده از کد باینری پنج بیتی، اطلاعات به ازای هر کاراکتر:
مثال 6.اجازه دهید یک پیام (یک کلمه به زبان روسی) از طریق کانال ارتباطی رمزگذاری شده با کد شانون-فانو دریافت شود: 10111001110010010010100.
رمزگشایی دنباله داده شده ضروری است.
راه حل:فرآیند رمزگشایی بر اساس خاصیت پیشوند کد است و از چپ به راست انجام می شود. جدول 3 نشان می دهد که حداقل طول کد سه بیت است. از ابتدای کلمه رمز دریافتی سه بیت را می شمارد، می گیریم - 101. چنین کدی در جدول وجود ندارد، بنابراین یک بیت دیگر اضافه می کنیم، 1011 می کنیم. این کد نیز در جدول نیست، بنابراین، آن است. لازم است یک بیت دیگر اضافه کنیم، ترکیبی را دریافت می کنیم - 10111، که مربوط به حرف "k" است. کلمه رمز 10111 از کلمه رمز دریافتی حذف شده و با نماد اصلی (حرف "ک") جایگزین می شود. روند رمزگشایی بقیه حروف پیام دریافت کردبه روشی مشابه انجام می شود.
فرآیند رمزگشایی کامل در جدول 4 نشان داده شده است. علامت "-" در جدول به این معنی است که کد انتخاب شده در جدول 3 وجود ندارد.
جدول 4
فرآیند رمزگشایی پیام
| دنباله کد دریافت شد | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| به | ||||||||||||||||||||||
| به | O | |||||||||||||||||||||
| به | O | - | ||||||||||||||||||||
| به | O | - | ||||||||||||||||||||
| به | O | - | ||||||||||||||||||||
| به | O | د | ||||||||||||||||||||
| به | O | د | - | |||||||||||||||||||
| به | O | د | ه | |||||||||||||||||||
| به | O | د | ه | - | ||||||||||||||||||
| به | O | د | ه | - | ||||||||||||||||||
| به | O | د | ه | آر |
پس کلمه ای که در نتیجه رمزگشایی کلمه رمز دریافتی به دست می آید «رمزگذار» است.
رمزگذاری بهینه
قضیه کدگذاری شانون. روش های کدگذاری بهینه حرف به حرف معیارهای بهینه بودن کد رمزگذاری را مسدود کنید. یک سیستمرمزگذاری اطلاعات متنی
کد نویسی,به حداقل رساندن افزونگی کد,بهینه نامیده می شود.
مسئله وجود چنین کدهایی جوهره یکی از قضایای اصلی نظریه اطلاعات است - قضیه کدگذاری که توسط K. Shannon اثبات شده است. در اینجا یکی از فرمول های معادل این قضیه وجود دارد.
قضیه کدگذاری. پیام های منبع اطلاعات دلخواه Z با آنتروپی H(ز)همیشه می توان با دنباله هایی در الفبای B کدگذاری کرد,متشکل از کاراکتر M,بنابراین,که میانگین طول کلمه رمز به طور دلخواه نزدیک به مقدار خواهد بود 
,اما نه کمتر از او
به دلیل پیچیدگی آن، اثبات این قضیه در نظر گرفته نمی شود.
این قضیه بیان می کند که تفاوت را می توان به طور دلخواه کوچک کرد. این وظیفه روش های کدگذاری بهینه است.
بیایید به بررسی یک منبع اطلاعاتی الفبایی برگردیم که پیام ها را با حروف الفبایی تولید می کند. آ... از آنجایی که افزونگی کد با فرمول داده می شود
واضح است که هر چه کد کمتر، بهینه تر باشد. برای کاهش کاراکترهای متداول باید با کلمات کوتاه تر کدگذاری شوند و بالعکس. تمام روش های کدگذاری بهینه بر اساس این نیاز است. علاوه بر این، برای اطمینان از رمزگشایی یک کد ناهموار، مهم است که رعایت کنید اصل پیشوند: هیچ کلمه رمزی نباید شروع کلمه رمز دیگری باشد.
در اینجا دو مورد از شناخته شده ترین روش های کدگذاری بهینه حرف به حرف آورده شده است. برای سادگی، ما می گیریم الفبای دوتاییبه عنوان یک کد
مرحله 1. نمادهای الفبای اصلی را به ترتیب عدم افزایش احتمال آنها مرتب می کنیم. (آنها را روی یک رشته می نویسیم.)
مرحله 2. بدون تغییر ترتیب نمادها، آنها را به دو گروه تقسیم می کنیم تا کل احتمالات نمادها در گروه ها تا حد امکان برابر باشد.
مرحله 3. ما به گروه در سمت چپ "0" و به گروه سمت راست "1" به عنوان عناصر کد آنها اختصاص می دهیم.
مرحله 4. گروه ها را مرور کنید. اگر تعداد عناصر در گروه بیش از یک است، به مرحله 2 بروید. اگر یک عنصر در گروه وجود دارد، ساخت کد برای آن کامل شده است.
برنج. 4.1. درخت دودوییمربوط به کدگذاری شانون - فانو
عملکرد الگوریتم توصیف شده را با استفاده از مثال کدگذاری الفبا در نظر بگیرید 
که نمادهای آن به ترتیب با احتمالات (25/0؛ 05/0؛ 25/0؛ 1/0؛ 25/0؛ 1/0) رخ می دهند. نتیجه کدگذاری در شکل نشان داده شده است. 4.1.
بدیهی است که فرآیند ساخت کد در حالت کلی حاوی ابهام است، زیرا ما همیشه نمی‌توانیم دنباله را به دو زیرمجموعه با احتمال مساوی تقسیم کنیم. چه در سمت چپ و چه در سمت راست، مجموع احتمالات بیشتر خواهد بود. معیار بهترین حالت، افزونگی کمتر کد است. همچنین توجه داشته باشید که خواندن صحیح کد - از ریشه درخت تا نماد - از پیشوند بودن آن اطمینان حاصل می کند.
