Abstract

Linear interactive encoding and decoding (IED) for near lossless source coding with decoder only side information is considered, where the interactive encoder uses linear codes (described by parity-check matrices over a finite field X) for encoding. It is first demonstrated how to convert any classical universal lossless code Cn (with block length n and with side information available to both the encoder and decoder) into a universal random linear IED scheme based on Gallager's parity check ensemble. It is then shown that there is no performance loss by restricting IED to linear IED, and that the universal random linear IED scheme based on Gallager's parity check ensemble achieves essentially the same rate performance as does Cn for each and every individual sequence pair (xn, yn) while the word decoding error probability goes to 0 as n → ∞ . Define the density of a linear IED scheme as the percentage of nonzero entries in its parity-check matrix. To reduce the encoding complexity of linear IED, low density linear IED is further investigated in terms of the trade-off among its rate, decoding error probability, and density

چکیده 

 در این مقاله قصد داریم مسئله‌ی رمزگذاری و رمز گشائی تعاملی خطی (IED)  را به‌منظور سورس کدینگ( کد نویسی منبع)  بدون اتلاف با اطلاعات جانبی موجود در اختیار دیکدر مطرح می‌سازیم، که در این مسئله، رمزگذار تعاملی(فعل و انفعالی)  از کدهای خطی ( که به‌وسیله‌ی ماتریس‌های بررسی توازن بر روی یک میدان محدود x تشریح می‌شوند) استفاده نموده تا بتواند پروسه‌ی رمزگذاری را انجام دهد. در ابتدا نشان خواهیم داد که چطور می‌توان هر نوع کد بدون اتلاف جهانی  ( با طول بلاک n و موجود بودن اطلاعات در سمت انکدر و دیکدر) را به یک شِمای IED خطی تصادفی جهانی و مبتنی بر ساختار کلیِ بررسی توازن گالگر  تبدیل کرد. به دنبال آن، نشان خواهیم داد که با محدودسازی IED به IED خطی، شاهد هیچ افت کارایی نخواهیم بود و  همچنین نشان خواهیم داد که شِمای IED خطی و تصادفی جهانی- که مبتنی بر ساختار کلی بررسی توازن گالگر می‌باشد، - درزمانی که احتمال خطای رمز گشائی کلمه به سمت صفر میل می‌کند -،  ضرورتاٌ  می‌تواند به همان نرخ کارائی مشابه با  برای هر زوج دنباله‌ی   دست پیدا کند. در ادامه، چگالی شِمای IED خطی را به‌عنوان درصدی از ورودی‌های غیر صفر در ماتریس بررسی توازن آن تعریف خواهیم کرد. به‌منظور کاهش پیچیدگی رمزگذاری در IED خطی، IED خطی با چگالی پایین را برحسب ایجاد موازنه در بین نرخ، احتمال خطای رمز گشائی و چگالی، بررسی خواهیم کرد.

1-مقدمه 

اخیراٌ مفهوم رمزگذاری و رمز گشائی فعل و انفعالی (IED) به‌صورت رسمی در [1],[2] معرفی گردیده است. یک مورد خاصی از یک IED برای  یادگیری یک‌طرفه (و تقریباٌ ) بدون اتلاف ( به‌عبارت‌دیگر، رمزنگاری بدون اتلاف منبع) با  اطلاعات جانبی که فقط در اختیار دیکدر می‌باشد، در شکل نشان داده‌شده است که در این شکل، X یک منبع الفبای محدودی را نشان داده که باید توسط دیکدر یادگیری شده، Y نیز منبع الفبای محدود دیگری را نشان می‌دهد که  مرتبط با x بوده و فقط  به‌عنوان اطلاعات جانبی در اختیار دیکدر قرار داشته، و R نیز تعداد  میانگین بیت‌ها ( که کارائی شِمای IED را اندازه‌گیری می‌کند) را به ازای هر سمبلی که بین دیکدر و انکدر مبادله شده است نشان می‌دهد. در شکل 1 مشاهده می‌شود که تفاوت اصلی در بین IED و  روش کدینگ Slepain-Wolf   در این بوده که در IED، دیکدر و انکدر مجاز به تعامل با یکدیگر می­باشند تا اینکه پروسه‌ی یادگیری ( یا کدینگ منبع) انجام شود...