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

توابعی که نرخ و اعوجاج را به هم مرتبط می‌کنند، جواب‌های مسئلهٔ کمینه سازی زیر هستند:
\inf _{Q_{Y|X}(y|x)}I_{Q}(Y;X)\ {\mbox{subject to}}\ D_{Q}\leq D^{*}.
در اینجا (QY | X(y | x، که گاهی تست کانال نامیده می‌شود، تابع چگالی احتمال شرطی (PDF) خروجی کانال ارتباطی Y برای یک ورودی مفروض X است و (IQ(Y ; X اطلاعات متقابل بین Y و X است که به صورت زیر تعریف می‌شود:
I(Y;X)=H(Y)-H(Y|X)\,
که (H(Y و (H(Y | X آنتروپی سیگنال خروجی (y) و آنتروپی شرطی سیگنال خروجی به شرط سیگنال ورودی است :
H(Y)=-\int _{-\infty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy
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.همچنین مسئله را می‌توان به صورت یک تابع نرخ-اعوجاج فرمول بندی کرد که قصد داریم آن را روی اعوجاج‌های دست یافتنی برای یک محدودیت روی نرخ مینیمم کنیم. عبارت مرتبط با آن به صورت خواهد بود:
\inf _{Q_{Y|X}(y|x)}E[D_{Q}[X,Y]]\ {\mbox{subject to}}\ I_{Q}(Y;X)\leq R.
این دو فرمول بندی به توابعی منجر می‌شود که معکوس یکدیگر هستند.
اطلاعات متقابل می‌تواند به عنوان معیاری باشد برای تفاوت عدم قطعیت گیرنده از سیگنال 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 برای یک(QY | 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 شرطی ای (QY | X(y | x می‌رود که نرخ را برای یک اعوجاج D* کمینه کند.
یک تعریف آنالیزی برای حل این مسئلهٔ کمینه سازی، اغلب سخت بدست می‌آید، جز در مواردی که به دو مورد از آنها اشاره می‌کنیم. تابع نرخ-اعوجاج هر منبع از چند ویژگی اساسی پیروی می‌کند. مهم ترینشان این است که یک تابع پیوستهٔ اکیداً نزولی مقعر است.
اگر چه جواب آنالیتیکال برای این مسائل نادر است، حد بالا و پایینی نظیر حد پایین شانون (SLB) برای این توابع وجود دارد، که در مورد خطای مربع و منبع بی حافظه، عنوان می‌کند که برای هر منبع دلخواه با آنتروپی تفاضلی محدود داریم:
R(D)\geq h(X)-h(D)\,
که(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}):E[d(X^{n},Y^{n})]\leq D\}
که بالانویس‌ها یک دنباله کامل تا آن زمان را نشان میدهد و زیرنویس 0، حالت اولیه را نشان می‌دهد.