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

در نظریهٔ کدگذاری، رمزگشایی (به انگلیسی: 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$ بعد از انتقال دریافت می‌شود.

توافقات رمزگشایی

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

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

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

اطلاعات بیشتر: برآورد درست‌نمایی بیشینه

با دریافت یک بردار $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{aligned}\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{aligned}}$

با ثابت کردن $\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. 190. [[:en:ISBN|-(identifier) ISBN 0-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. 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. 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