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

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

نمادگذاری

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

رمزگشایی ناظر ایده‌آل

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

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

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

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

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

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

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

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

$\begin{array}{cc}\mathbb{P}(x\text{ received}\mid y\text{ sent})& =\frac{\mathbb{P}(x\text{ received},y\text{ sent})}{\mathbb{P}(y\text{ sent})}\\ & =\mathbb{P}(y\text{ sent}\mid x\text{ received})\cdot \frac{\mathbb{P}(x\text{ received})}{\mathbb{P}(y\text{ sent})}.\end{array}$

با ثابت کردن $\mathbb{P}(x\text{ received})$ ، $x$ بازساخته می‌شود و $\mathbb{P}(y\text{ sent})$ ثابت است زیرا همه کدواژه‌ها به یک اندازه احتمال ارسال دارند؛ بنابراین، $\mathbb{P}(x\text{ received}\mid y\text{ sent})$ به عنوان تابعی از متغیر $y$ به حداکثر می‌رسد دقیقاً زمانی که $\mathbb{P}(y\text{ sent}\mid x\text{ 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