نظریه نرخ-اعوجاج

نظریه نرخ اعوجاج یک شاخه اصلی از نظریه اطلاعات است که اصول نظری برای فشرده سازی داده دارای خطا است. این نظریه سعی در حل مسئله مشخص کردن حداقل تعداد بیت برای هر سمبل است (که با نرخ R اندازه گرفته می‌شود) که باید در کانال انتقال یابد بگونه‌ای که منبع اولیه را بتوان به صورت تقریبی در مقصد بازیابی کرد، ضمن اینکه اعواج از حد معینی (D) بیشتر نشود.
مقدمه
نظریه نرخ-اعوجاج یک صورت بندی ریاضی ارائه می‌کند که جه مقدار فشرده سازی از نوع خطا دار امکان‌پذیر است. بسیاری از روش‌های فشرده سازی، صدا، گفتار، تصویر و فیلم دارای تبدیلات، کوانتیزاسیون، و روندهایی برای اختصاص نرخ بیت هستند که در قالب کلی توابع نرخ - اعوجاج تجمیع می‌شود.
نظریه نرخ-اعوجاج توسط شنون در کار اساسیش در نظریه اطلاعات ساخته شد.
در نظریه نرخ-اعوجاج، نرخ معمولات به عنوان تعداد بیت مورد استفاده برای هر سمبل به منظور ارسال یا ذخیره‌سازی شناخته می‌شود. مفهوم اعوجاج نیز موضوعی است که به آن در ادامه خواهیم پرداخت. در بسیاری از موارد ساده اعوجاج به صورت امید ریاضی مربع اختلاف بین سیگنال ورودی و خروجی تعریف می‌شود. اما، از آنجایی که تکنیک‌های فشرده سازی خطا دار روی داده گانی اعمال می‌شوند که قرار است برای انسان قابل درک باشد ،(نظیر گوش دادن به موسیقی، تماشای تصاویر و فیلم) اندازه‌گیری اعواج باید بگونه‌ای مدل شود که متناسب بادرک انسان باشد. بسیار شبیه استفاده از احتمال در فشرده سازی خطا دار، سنجه‌های اعوجاج می‌توانند با توابع هزینه (همان گونه که در تخمین بیزین و تئوری تصمیم استفاده می‌شود)، شناخته شوند. در فشرده سازی صوت، مدل‌های ادراکی (و در نتیجه اعوجاج ادراکی) نسبتا خوب پیشرفت کرده‌اند و به صورت معمول در تکنیک‌های فشرده سازی نظیر MP3 یا Vorbis استفاده می‌شوند، اما اغلب ساده نیست که در غالب تئوری نرخ- اعوجاج آورده شود. در فشرده سازی تصویر و فیلم، مدل‌های مبتنی بر ادراک انسان کمتر توسعه یافته‌اند و به صورت محدود در ماتریس وزن‌های JPEG وMPEG استفاده می‌شود.
توابع نرخ - اعوجاج
توابعی که نرخ و اعوجاج را به هم مرتبط می‌کنند، جواب‌های مسئله کمینه سازی زیر هستند:
در اینجا (Q Y | X (y | x، که گاهی تست کانال نامیده می‌شود، تابع چگالی احتمال شرطی (PDF) خروجی کانال ارتباطی Y برای یک ورودی مفروض X است و (I Q (Y ; X اطلاعات متقابل بین Y و X است که به صورت زیر تعریف می‌شود:
که (H(Y و (H(Y | X آنتروپی سیگنال خروجی (y) و آنتروپی شرطی سیگنال خروجی به شرط سیگنال ورودی است :
H(Y|X) =
- \int_{-\infty^{\infty \int_{-\infty^\infty Q_{Y|X(y|x) P_X (x) \log_{2 (Q_{Y|X (y|x))\, dx\, dy. همچنین مسئله را می‌توان به صورت یک تابع نرخ - اعوجاج فرمول بندی کرد که قصد داریم آن را روی اعوجاج‌های دست یافتنی برای یک محدودیت روی نرخ مینیمم کنیم. عبارت مرتبط با آن به صورت خواهد بود:
این دو فرمول بندی به توابعی منجر می‌شود که معکوس یکدیگر هستند.
اطلاعات متقابل می‌تواند به عنوان سنجه‌ای باشد برای تفاوت عدم قطعیت گیرنده از سیگنال Y و عدم قعطعیت از Y به شرط دانستن X. البته این کاهش عدم قطعیت به خاطر میزان اطلاعاتی است که بین فرستنده و گیرنده مخابره می‌شود. (I(Y; X
به عنوان مثال، اگر هیچ مخابره‌ای نداشته باشیم، آنگاه (H(Y |X) = H(Y و I(Y; X) = ۰. در طرف دیگر، اگر کانال مخابراتی بدون خطا باشد و سیگنال دیافتی Y برابر سیگنال ارسالی X باشد، آنگاه H(Y | X) = ۰ و (I(Y; X) = H(Y.
در تعریف نرخ- اعوجاج، اعوجاج بین X و Y برای یک(Q Y | X (y | x هستند و حداکثر اعوجاج مجاز هستند. هنگامی که از میانگین مربع خطا به عنوان سنجه اعواج استفاده می‌کنیم، داریم: (برای سیگنال‌های با دادمنه پیوسته)
D_Q = \int_{-\infty^\infty \int_{-\infty^\infty
P_{X,Y(x,y) (x-y)^2\, dx\, dy = \int_{-\infty^\infty \int_{-\infty^\infty
Q_{Y|X(y|x)P_{X(x) (x-y)^2\, dx\, dy. همان‌طور که معادله بالا نشان می‌دهد، محاسبه یک تابع نرخ - اعوجاج نیاز به توصیف احتمالی ورودی X در قالب PDF آن دارد، و سپس به دنبال PDF شرطی‌ای (Q Y | X (y | x می‌رود که نرخ را برای یک اعوجاج D * کمینه کند.
یک تعریف آنالیزی برای حل این مسئله کمینه سازی، اغلب سخت بدست می‌آید، جز در مواردی که به دو مورد از آنها اشاره می‌کنیم. تابع نرخ - اعوجاج هر منبع از چند ویژگی اساسی پیروی می‌کند. مهمترینشان این است که یک تابع پیوسته اکیدا نزولی مقعر است.
اگر چه جواب آنالیتیکال برای این مسائل نادر است، حد بالا و پایینی نظیر حد پایین شنون (SLB) برای این توابع وجود دارد، که در مورد خطای مربع و منبع بی‌حافظه، عنوان می‌کند که برای هر منبع دلخواه با آنتروپی تفاضلی محدود داریم:
که(h(D آنتروپی تفاضلی متغیر تصادفی گاوسی با واریانس D است. این حد پایین قابل تعمیم به منابع حافظه دار و سایر سنجه‌های اعوجاج است. یک ویژگی مهم SLB این است که در شرایط اعوجاج اندک برای گروه وسیعی از منابع باند سفتی در دسترس قرار می‌دهد.
الگوریتم Blahut–Arimoto یک روش مبتنی بر تکرار برای حل عددی تابع نرخ - اعوجاج برای الفبای محدود ورودی - خروجی منبع است و کارهای زیادی برای گسترش این راه حل به مسائل عمومی‌تری انجام شده است.
هنگام کار با منابع پایستار و حافظه دار، ضروری است که تعریف تابع نرخ - اعوجاج بازنگری شود و به صورت یک حد روی دنباله‌هایی که طول افزایشی دارد دیده شود.
R(D) = \lim_{n \rightarrow \infty R_n(D)
جایی که:
R_n(D) = \frac{1{n \inf_{Q_{Y^n|X^n \in \mathcal{Q I(Y^n, X^n)
و
\mathcal{Q = \{ Q_{Y^n|X^n(Y^n|X^n,X_0): Ed(X^n,Y^n) \leq D \
جایی که بالانویس‌ها یک دنباله کامل تا آن زمان را نشان میدهدو زیرنویس ۰ حالت اولیه را نشان می‌دهد.
منبع گوسی بی‌حافظه (مستقل)
اگر فرض کنیم که (P X (x یک گاوسی با واریانس  2 و نمونه‌های آتی سیگنال X، احتمالاتی مستقل هستند (یا معادلا، منبع بی‌حافظه است یا سیگنال‌ها نا همبسته این)، فرم بسته زیر برای تابع نرخ - اعوجاج استخراج می‌شود:
R(D) = \left\{ \begin{matrix
\frac{1{2\log_2(\sigma_x^2/D ), - \mbox{if 0 \le D \le \sigma_x^2 \\ \\
0, - \mbox{if D> \sigma_x^2.
\end{matrix \right.
شکل زیر نشان می‌دهد که این تابع بدین صورت است:
پرونده:Rate distortion function.png
نظریه نرخ - اعوجاج به ما می‌گوید هیچ سیستم فشرده سازی وجود ندارد که خارج از ناحیه خاکستری عمل کند. خط قرمز یک باند برای فشرده سازهای عملی است. به عنوان یک قانون کلی این حد تنها با افزایش طول بلوک‌های کد امکان‌پذیر است. با این وجود، حتی در طول بلوک واحد امکان یافتن کوانتایز خوب بگونه‌ای که با فاصله خوبی از تابع نرخ - اعوجاج کار کند وجود دارد.
این تابع نرخ - اعوجاج تنها برای منابع گاوسی بدون حافظه برقرار است. منبع گاوسی سخترین منبع برای دیکد کردن است. برای یک خطای میانگین مربعات، این منبع به بیشترین تعداد بیت نیاز دارد. بهره‌وری یک سیستم فشرده سازی عملی که بر روی تصاویر کار می‌کند ممکن است به خوبی زیر باند پایین (R(D نشان داده شده باشد.
اتصال نظریه نرخ - اعوجاج با ظرفیت کانال
فرض کنید که قصد داریم اطلاعاتی را در مورد منبع به کاربر ارسال کنیم بطوری که اعوجاج از حد D تجاوز نکند. نظریه نرخ - اعوجاج می‌گوید که حداقل (R(D بیت برای هر سمپل از اطلاعات از منبع باید به کاربر برسد. همچنان از تئوری کدینگ کانال شنون می‌دانیم که اگر آنتروپی منبع H بیت برای هر سمبل باشد، و ظرفیت کانال (C (C<H باشد، آنگاه H-C بیت برای هر سمبل هنگام ارسال اطلاعات روی کانال داده شده از دست می‌رود. برای اینکه کاربر بتواند شانسی برای بازیابی اطلاعات با حداکثر اعوجاج D باشد، باید این ضرورت را تحمیل کنیم که از دست دادن اطلاعات در یک انتقال از بیشنه خطای قابل تحمل (H − R(D بیت برای هر سمیل بیشتر نباشد؛ که این به این معنی است که ظرفیت کانال باید حداقل بیشتر از (R(D باشد.
Decorrelation
بهینه‌سازی نرخ - اعوجاج
کد گذاری منبع
بسته‌بندی - کروی
سفید کردن (مربوط به نویز)
Blahut-Arimoto الگوریتم