روش‌های رمزگشایی

در نظریهٔ کدگذاری، **رمزگشایی ([[زبان انگلیسی|به انگلیسی:]] decoding)** فرایند ترجمهٔ پیام‌های دریافتی به کدواژه‌های (به انگلیسی: codeword) یک کد معین است. روش‌های مختلفی برای نگاشت پیام‌ها به کدواژه‌ها وجود دارد که معمولاً برای بازیابی پیام‌های ارسال‌شده از طریق یک کانال نویزی، مانند یک کانال دودویی متقارن (به انگلیسی: binary symmetric channel) استفاده می‌شوند.

## نمادگذاری
کد C \subset \mathbb{F}_2^n یک کد باینری با طول n است؛ x,y عناصری از \mathbb{F}_2^n هستند؛ و d(x,y) فاصله بین این عناصر را نشان می‌دهد.

## رمزگشایی ناظر ایده‌آل
اگر پیام x \in \mathbb{F}_2^n داده شده باشد، **رمزگشایی ناظر ایده‌آل ([[زبان انگلیسی|به انگلیسی:]] ideal observer decoding)** کدواژه y \in C را تولید می‌کند. فرایند به این صورت است که:

\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})

به عنوان مثال، شخص می‌تواند کدواژه y را انتخاب کند که احتمالاً به عنوان پیام x بعد از انتقال دریافت می‌شود.

### توافقات رمزگشایی
هر کدواژه یک احتمال مورد انتظار ندارد: ممکن است بیش از یک کدواژه با احتمال برابر برای تغییر به پیام دریافتی وجود داشته باشد. در چنین مواردی، فرستنده و گیرنده باید از قبل بر سر یک توافق رمزگشایی با یکدیگر به توافق برسند. توافقات محبوب شامل موارد زیر است:

:# درخواست برای ارسال مجدد کدواژه - درخواست بازفرستی خودکار (به انگلیسی: automatic repeat-request).
:# انتخاب هر کدواژه تصادفی از مجموعه کدواژه‌های محتمل‌تر که به پیام نزدیک‌تر هستند.
:# اگر کد دیگری دنبال شود، بیت‌های مبهم کدواژه را به عنوان پاک‌شدگی علامت بزنید و امیدوار باشید که کد بیرونی (به انگلیسی: outer  code) آن‌ها را شفاف‌سازی کند.
:# گزارش یک شکست رمزگشایی به سیستم.

## رمزگشایی درست نمایی بیشینه

با دریافت یک بردار x \in \mathbb{F}_2^n **رمزگشایی درست نمایی بیشینه ([[زبان انگلیسی|به انگلیسی:]] maximum likelihood decoding)** کدواژه y \in C را انتخاب می‌کند که بیشترین مقدار\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) را به دست می‌آورد، یعنی کدواژه y که احتمال دریافت پیام x با فرض ارسال y را به حداکثر می‌رساند. اگر همه کدواژه‌ها به یک اندازه احتمال ارسال داشته باشند، این طرح معادل با رمزگشایی ناظر ایده‌آل است. در واقع، با استفاده از قضیه بیز (به انگلیسی:  Bayes Theorem),


\begin{align}
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) & {} = \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent} )} \\
& {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}) \cdot \frac{\mathbb{P}(x \mbox{ received})}{\mathbb{P}(y \mbox{ sent})}.
\end{align}


با ثابت کردن \mathbb{P}(x \mbox{ received}) ، x بازساخته می‌شود و \mathbb{P}(y \mbox{ sent}) ثابت است زیرا همه کدواژه‌ها به یک اندازه احتمال ارسال دارند؛ بنابراین، 
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})
 به عنوان تابعی از متغیر y به حداکثر می‌رسد دقیقاً زمانی که 
\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} )
 به حداکثر می‌رسد، و ادعا تأیید می‌شود.

همانند رمزگشایی ناظر ایده‌آل، باید توافقی برای رمزگشایی غیرمنحصربه‌فرد (به انگلیسی: non-unique) برقرار شود.

مسئله رمزگشایی درست نمایی بیشینه نیز می‌تواند به عنوان یک مسئله برنامه‌نویسی صحیح (به انگلیسی: integer programming)

مدل‌سازی شود.

الگوریتم رمزگشایی درست نمایی بیشینه یک نمونه از مسئله «به حداکثر رساندن تابع ضرب» است که با اعمال قانون توزیعی تعمیم‌یافته (به انگلیسی: generalized distributive law) حل می‌شود.

## جستارهای وابسته
* حالت بی‌اهمیتی
* تشخیص و تصحیح خطا
* Forbidden input

## منابع

* Feldman, Jon; Wainwright, Martin J. ; Karger, David R. (مارس ۲۰۰۵). "Using Linear Programming to Decode Binary Linear Codes". IEEE Transactions on Information Theory. 51 (3): 954–972. CiteSeerX 10.1.1.111.6585. doi:10.1109/TIT.2004.842696. S2CID 3120399.
* Aji, Srinivas M. ; McEliece, Robert J. (مارس ۲۰۰۰). "The Generalized Distributive Law" (PDF). IEEE Transactions on Information Theory. 46 (2): 325–343. doi:10.1109/18.825794.
* Beutelspacher, Albrecht; Rosenbaum, Ute (1998). Projective Geometry. Cambridge University Press. p.&nbsp;190. [-(identifier) ISBN 0-[:en:Special:BookSources/0-521-48277-1|521-48277-1.
* Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. Springer-Verlag. pp.&nbsp;106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.
* Ohta, Kazuo; Pei, Dingyi, eds. (1998). Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp.&nbsp;187–199. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.
* Siamack Ghadimi (2020), Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;, Universal Journal of Electrical and Electronic Engineering

رده:نظریه کدگذاری