کدگذاری گولومب

رمزگذاری Rice (اختراع شده توسط رابرت اف. رایس ) به استفاده از زیرمجموعه‌ای از خانواده کدهای Golomb، برای تولید یک رمز پیشوندی ساده‌تر (اما نه لزوما بهینه) اشاره دارد. رایس از این مجموعه رمزها در یک قالب رمز گذاری انطباقی استفاده کرد. منظور از "رمزگذاری رایس" همچنین می‌تواند آن قالب رمزگذاری انطباقی و یا استفاده از آن زیر مجموعه از کدهای Golomb باشد. در حالی که رمزگذاری Golomb دارای یک پارامتر قابل تنظیم است که می‌تواند هر عدد صحیح مثبت باشد، کدهای رایس آن‌هایی هستند که پارامتر قابل تنظیم آن، عددی به صورت ${\displaystyle 2^{n}}$ است. از آنجایی که کامپیوتر‌ها با منطق دودویی کار می‌کنند، این امر باعث می‌شود تا رمزگذاری رایس برای استفاده در کامپیوتر بسیار راحت باشد زیرا به راحتی می‌توان آن را در عدد 2 ضرب و تقسیم کرد.

رایس بسیار علاقه‌مند بود تا این زیرمجموعه ساده‌تر را ارائه کند؛ به این دلیل که توزیع‌های هندسی اغلب با زمان تغییر می‌کنند، یا که دقیقاً شناخته شده نیستند و یا هر دو. بنابراین انتخاب رمز به ظاهر بهینه ممکن است چندان سودمند نباشد.

رمزگذاری رایس به عنوان مرحله رمزگذاری آنتروپی در تعدادی از روش های فشرده سازی تصویر بدون اتلاف و فشرده سازی داده‌های صوتی استفاده می‌شود.

به روش زیر توجه کنید. این رمزگذاری Rice-Golomb است، به طوری که رمز باقیمانده از رمزگذاری دودویی منقطع ساده استفاده می‌کند، که همچنین با نام "رمزگذاری رایس" نیز شناخته می‌شود (سایر رمزگذاری های با طول متغیر دودویی، مانند رمزگذاری های حسابی یا هافمن، برای رمزهای باقیمانده نیز امکان پذیر است؛ اگر توزیع آماری رمزهای باقیمانده خطی و مسطح نباشد، و خصوصاً وقتی که همه باقی‌مانده‌های ممکن بعد از تقسیم استفاده نشده باشند). در این الگوریتم، اگر پارامتر M عددی به صورت ${\displaystyle 2^{n}}$ باشد، معادل ساده ای از رمزگذاری رایس می‌شود.

1. پارامتر M را بر روی یک عدد صحیح ثابت قرار بده.
2. برای N (عددی که باید رمزگذاری شود)، تعیین کن:
   1. [quotient = q = int[N/M
   2. remainder = r = N%M
3. Codeword تولید کن
   1. قالب رمز: <Quotient Code> <Code Remainder> ، به صورتی که:
   2. رمز Quotient در رمزنگاری یگانی (unary):
      1. رشته‌ای به طول q از بیت 1 بنویس (جایگزین: رشته‌ای از بیت 0)
      2. یک بیت 0 بنویس (یا متناظراً یک بیت 1)
   3. رمز Remainder (در رمزگذاری دودویی منقطع )
      1. ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
         1. اگر ${\displaystyle r<2^{b+1}-M}$ بود: r را با استفاده از b بیت در نمایش دودویی رمز کن.
         2. اگر ${\displaystyle r\geq 2^{b+1}-M}$ بود: رقم ${\displaystyle r+2^{b+1}-M}$ را در نمایش دودویی با استفاده از b بیت 1 رمز کن.

فرض کنید M = 10 باشد. بدین ترتیب ${\displaystyle b=\lceil \log _{2}(10)\rceil =4}$. به طور خلاصه:

${\displaystyle 2^{b}-M=16-10=6}$

رمزگذاری خارج قسمت q خروجی 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 ${\displaystyle \vdots }$ ${\displaystyle \vdots }$ N ${\displaystyle \underbrace {111\cdots 111} _{N}0}$

رمزگذاری باقی مانده r انحراف دودویی خروجی 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

به عنوان مثال، با رمزگذاری Rice-Golomb با تعیین M = 10، عدد 42 در مبنای 10، ابتدا به q = 4 ،r = 2 تقسیم می‌شود و اینگونه رمزگذاری می‌شود:${\displaystyle {qcode(q),rcode(r)=qcode(4),rcode(2)=11110,010}}$(لازم نیست که ویرگول جداکننده را در جریان خروجی رمزگذاری کنید، زیرا 0 در انتهای کد q برای تعیین زمانی که q به پایان می رسد و r شروع می شود کفایت می‌کند؛ هر دو رمز qcode و rcode خودمحدودکننده هستند).

الفبایی شامل دو نماد یا مجموعه ای از دو رویدادِ P و Q به ترتیب با احتمال‌های p و ${\displaystyle {1-p}}$، به طوری که ${\displaystyle {p\geq 1/2}}$ داده شده است. رمزگذاری Golomb می‌تواند برای رمزگذاری تعدادی صفر یا چند P که توسط Q های تکی از هم جدا شده استفاده شود. در این کاربرد، بهترین مقدار پارامتر M، نزدیکترین عدد صحیح به ${\displaystyle {\frac {-1}{\log _{2}p}}}$ است . وقتی p = 1/2 ،M = 1 باشند و کد Golomb با یگانی مطابقت دارد ( ${\displaystyle {n\geq 0}}$ تا P و به دنبال آن یک Q به صورت n تا یک و به دنبال آن یک صفر رمزگذاری می‌شود). اگر رمز ساده‌تر مد نظر باشد، می‌توان پارامتر ${\displaystyle b}$ در Golomb-Rice (یعنی پارامتر ${\displaystyle M=2^{b}}$ گولومب) را مساوی نزدیکترین عدد صحیح به ${\displaystyle -\log _{2}(-\log _{2}p)}$ قرار داد؛ اگرچه ممکن است همیشه بهترین مقدار نباشد، اما معمولاً بهترین مقدار برای Rice است و عملکرد فشرده سازی آن خیلی نزدیک به رمز گولومبِ بهینه است. (خود رایس پیشنهاد داد تا از رمزهای مختلف برای داده های یکسان استفاده شود تا بفهمیم کدام یک بهترین روش است. بعد تر، محققی از آزمایشگاه JPL روش‌های مختلفی را برای بهینه سازی یا تخمین پارامتر برای رمز ارائه داد. )

استفاده از رمز رایس با یک قسمت دودویی که ${\displaystyle b}$ بیت برای به دنباله های رمزگذاری طول اجرا به طوری که در آن P دارای احتمال ${\displaystyle p}$ باشد را در نظر بگیرید. اگر ${\displaystyle \mathbb {P} [\mathbf {bit~is~part~of~} k\mathbf {-run} ]}$ احتمال این باشد که یک بیت بخشی از یک دنباله ${\displaystyle k}$ تایی باشد ( ${\displaystyle k-1}$ تا P و یک Q) و ${\displaystyle (\mathbf {compression~ratio~of~} k\mathbf {-run} )}$ نرخ فشرده سازی آن دنباله باشد، سپس نرخ فشرده سازی مورد انتظار به صورت زیر است:${\displaystyle {\begin{aligned}\mathbb {E} [\mathbf {compression~ratio} ]&=\sum _{k=1}^{\infty }(\mathbf {compression~ratio~of~} k\mathbf {-run} )\cdot \mathbb {P} [\mathbf {bit~is~part~of~} k\mathbf {-run} ]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}}$

فشرده سازی اغلب این گونه بیان می شود:${\displaystyle 1-\mathbb {E} [\mathbf {compression~ratio} ]}$ ، نسبت فشرده شده است. برای ${\displaystyle p\approx 1}$، روش رمزگذاری طول اجرا در نسبت فشرده سازی به آنتروپی نزدیک می‌شود. به عنوان مثال، با در استفاده از کد رایس، تعیین ${\displaystyle b=6}$ برای ${\displaystyle p=0.99}$، بازده ${\displaystyle 91.89\%}$ برای فشرده سازی را نتیجه می‌دهد، در حالی که حد آنتروپی ${\displaystyle 91.92\%}$ است.

هنگامی که توزیع احتمال برای اعداد صحیح شناخته شده نیست، نمی توان پارامتر بهینه برای رمزگذار Golomb-Rice را تعیین کرد. بنابراین، در بسیاری از برنامه‌ها، از یک رویکردِ دو-گذر استفاده می‌شود: اول، بلوک داده اسکن می‌شود تا یک تابع چگالی احتمال (PDF) برای داده‌ها را تخمین بزند. سپس پارامتر Golomb-Rice از PDF تخمین زده شده تعیین می‌شود. نوع ساده‌تر آن است که فرض کنیم PDF متعلق به یک خانواده پارامتری شده است، پارامترهای PDF را از داده ها برآورد کنیم، و سپس پارامتر بهینه Golomb-Rice را محاسبه کنیم. این رویکردی است که مورد استفاده در اکثر برنامه های مورد بحث در زیر است.

یک روش جایگزین برای اینکه داده های عدد صحیح که PDF آن مشخص نیست یا متغیر است را با بازدهی بالا رمزگذاری کنیم این است از رمزگذار سازگار-برگشتی استفاده کنیم. روش Run-length Golomb-Rice (RLGR) با استفاده از یک الگوریتم بسیار ساده که پارامتر Golomb-Rice را بر اساس آخرین نماد رمز شده، کم و زیاد می‌کند، این نتیجه را بدست می‌آورد. یک رمزگشا نیز می‌تواند از همان قاعده پیروی کند تا تغییرات پارامترهای رمزگذاری را ردیابی کند، بنابراین هیچ اطلاعات جانبی بجز داده های رمزگذاری، لازم نیست که منتقل شود. با فرض یک PDF Gaussian عمومی شده، که طیف گسترده‌ای از آماری را که در داده‌هایی از قبیل خطاهای پیش‌بینی دیده می‌شود یا ضرایب تبدیل‌شده در کدک‌های چندرسانه‌ای را نشان می‌دهد، الگوریتم رمزگذاری RLGR می‌تواند در چنین برنامه هایی عملکرد بسیار خوبی داشته باشد.

تعداد بیشماری از رمزگذارهای سیگنال‌ از رمز رایس برای باقی مانده‌های پیش بینی استفاده می‌کنند. در الگوریتم‌های پیش‌بینی، چنین باقیمانده‌هایی معمولاً در یک توزیع هندسی دو طرفه قرار می‌گیرند، در مقایسه با باقیمانده های بزرگ، باقی مانده های کوچک بیشتر از متداول هستند، و رمز رایس تخمین نزدیکی از رمز Huffman برای چنین توزیعی بدست می‌آورد با این تفاوت که سربار اینکه مجبور باشیم جدول هافمن را هم منتقل کنیم را نداریم. یک سیگنال که با هیچ توزیع هندسی‌ای مطابقت ندارد، یک موج سینوسی است، زیرا باقیمانده‌های دیفرانسیل یک سیگنال سینوسی ایجاد می‌کنند که مقادیر آن ایجاد یک توزیع هندسی نمی‌کنند (بالاترین و پایینترین مقادیر باقیمانده به طور مشابه دارای تکرار بالایی هستند، فقط مقادیر میانه مثبت و باقیمانده‌های منفی کمتر اتفاق می افتند).

چندین کدک صوتی بدون اتلاف، مانند Shorten، [4] FLAC ، [5] Apple Lossless و MPEG-4 ALS، بعد از مرحله پیش بینی خطی (که نام آن در Apple Lossless، "فیلتر تطبیقی FIR" است) از یک رمزگذاری رایس استفاده می کنند. همچنین از رمزگذاری رایس در کدک تصویری بدون اتلاف FELICS استفاده می‌شود.

رمزگذار Golomb-Rice در مرحله رمزگذاری آنتروپی کدگذاری بدون اتلاف تصاویر که مبتنی بر الگوریتم رایس هستند، استفاده می‌شود. یکی از این آزمایش‌ها منتج به نمودار نسبت فشرده‌سازی می‌شود که در پایین آمده است. نوشته های دیگر در این موضوع را در پایین همین صفحه مشاهده کنید. در این فشرده سازی‌ها، داده های دیفرانسیل فضای مترقی مجموعه ای متناوب از مقادیر مثبت و منفی در نزدیکی عدد 0 به دست می آورند، که به اعداد صحیح مثبت نگاشت می‌شوند (با دو برابر کردن مقدار مطلق و اضافه کردن عدد یک اگر ورودی منفی باشد) و سپس رمزگذاری رایس-گولومب با تغییر دادن مقسوم‌علیه که کوچک باقی می‌ماند، اعمال می‌شود.

نسبت‌های فشرده سازی آزمایش رایس با رمزگذاری Golomb

در این نتایج متوجه می‌شویم، رمزگذاری رایس ممکن است دنباله‌های بسیار طولانی از بیت 1 را برای خارج‌قسمت ایجاد کند. در عمل، اغلب لازم است که طول کل دنباله بیت‌هایی از 1، محدود شود؛ بنابراین یک نسخه اصلاح شده از رمزگذاری Rice-Golomb شامل جایگزین کردن رشته طولانی بیت 1 با رمزگذاری طول آن رشته توسط یک رمزگذاری بازگشتی رایس-گلومب است. برای انجام این کار لازم است برخی از مقادیر علاوه بر مقسوم علیه اولیه k، رزرو شوند تا تمایز لازم را ممکن‌سازد.

طرح‌واره JPEG-LS از رمز Rice-Golomb برای رمزگذاری باقیمانده‌های پیش‌بینی استفاده می‌کند.

(Run-length Golomb-Rice (RLGR نسخه تطبیقی از رمزگذاری Golomb-Rice که در بالا به آن اشاره شد، برای رمزگذاری محتوایات صفحه نمایش در ماشین‌های مجازی در اجزای RemoteFX پروتکل دسکتاپ از راه دور مایکروسافت مورد استفاده قرار می‌گیرد.

• رمزگذاری الیاس دلتا (δ)

• صفحه وب با نمونه‌ای عملی از رمزگذاری و رمزگشایی Golomb.

1. «کُدگذاری» [رایانه و فنّاوری اطلاعات] هم‌ارزِ «coding»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر دوم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۷-۰ (ذیل سرواژهٔ کُدگذاری)
2. Gallager, R. G.; van Voorhis, D. C. (1975). "Optimal source codes for geometrically distributed integer alphabets". IEEE Transactions on Information Theory. 21 (2): 228–230. doi:10.1109/tit.1975.1055357.
3. Merhav, N.; Seroussi, G.; Weinberger, M. J. (2000). "Coding of sources with two-sided geometric distributions and unknown parameters". IEEE Transactions on Information Theory. 46 (1): 229–236. doi:10.1109/18.817520.
4. "man shorten". Archived from the original on 2014-01-30. Retrieved 2008-12-07.
5. FLAC documentation: format overview