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

کدگذاری اطلاعات

مفاهیم اساسی

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

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

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

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

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

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

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

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

ل(n) = + 1 =] گزارش ( n + 1)[,

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

جدول 5.1

کد نویسی ه(n)

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

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

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

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

جدول 5.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

. (5.1)

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

,

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

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

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

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

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

. (5.2)

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

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

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

.

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

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

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

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

,

جایی که .

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

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

1 | |

برنامه دوره

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

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

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

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

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

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

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

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

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

ادبیات

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

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

3. Kolesnik V., Poltyrev G. Course of Information Theory, Science, 1982.

4. Feinstein A. Foundations of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Error-correcting codes, M., Mir, 1976.

6. Bärlekamp، نظریه کدگذاری جبری، M.، Mir، 1971.

اثر به سایت اضافه شد: 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 و یک مجموعه دلخواهسی ... نمایش مجموعه دلخواهسی به انواع کلمات در الفبا B تماس بگیرید D -با کدگذاری مجموعه 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 =] گزارش (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 k - l (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, ...) در صورت عدم وجود کلمه پیشوند نامیده می شود v k آغاز (پیشوند) هیچ کلمه ای نیست 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،د - 1) با طول n 1، n 2، ...، n N ، برای نابرابری لازم و کافی است

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

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

بدیهی است که کلمه رمز طولک دقیقا منع می کند D n - k قله های انتهایی ممکن (قله های آخرین سطح). سپس همه کدهای کد پیشوند، رئوس انتهایی را ممنوع می کنند. از آنجایی که تعداد کل رئوس انتهایی است D n ، سپس نابرابری

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

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

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

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

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

. (5.1)

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

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

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

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

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

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

. (5.2)

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

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

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

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

از آنجایی که نابرابری کرافت برای این انتخاب حفظ شده است، می توان کد پیشوند مربوطه را ساخت. زیرا 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) برای میانگین طول یک کلمه رمز در هر نماد برآورده می شود.

علاوه بر این، از آنجایی که حداقل طول کلمه رمز قابل دستیابی در هر نماد مقدار است، پس برایدی = 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 =] گزارش (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. مراحل بالا را به ترتیب برای هر یک از قسمت ها جداگانه تکرار می کنیم. Vدر نتیجه دریافت می کنیم:

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).

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

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

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

"xml: lang =" ru-RU "lang =" ru-RU "> رمزگذاری فانو

"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
a 2	] 2.321… [= 3	0.2	001	001
a 3	] 2.395… [= 3	0.4	011	01
a 4	] 3.058… [= 4	0.59	1001	100
a 5	] 3.183… [= 4	0.71	1011	101
a 6	] 3.472… [= 4	0.82	1101	110
a 7	] 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... در این صورت لازم است تمامی گروه های ممکن حروف با طول معین را به دست آورد، احتمالات گروه ها را به عنوان احتمال ظاهر مشترک حروف گروه به طور همزمان پیدا کرد و با توجه به گروه ها به عنوان نمادهای الفبای جدید.

PAGE 43