موضوع مقاله: کدگذاری گولومب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کدگذاری گولومب | مقدمه: کدگذاری گولومب یا رمزگذاری گولومب یک روش فشرده سازی بدون اتلاف اطلاعات است از خانواده‌ای از رمزهای فشرده سازی داده که توسط سلیمان دبلیو گلومب در دهه 1960 ابداع شده است. | ## بخش 1: کدگذاری گولومب | حروف الفبایی از یک توزیع هندسی تبعیت می‌کنند، از رمزنگاری Golomb به عنوان یک رمز پیشوندی مطلوب استفاده می کنند. باعث می‌شود که رمزگذاری Golomb بسیار مناسب برای موقعیت‌هایی باشد که در آن احتمال وقوع مقادیر کوچک در جریان ورودی، به طور قابل توجهی نسبت به مقادیر بزرگ بیشتر است. رایس ) به استفاده از زیرمجموعه‌ای از خانواده کدهای Golomb، برای تولید یک رمز پیشوندی ساده‌تر (اما نه لزوما بهینه) اشاره دارد. منظور از "رمزگذاری رایس" همچنین می‌تواند آن قالب رمزگذاری انطباقی و یا استفاده از آن زیر مجموعه از کدهای Golomb باشد. در حالی که رمزگذاری Golomb دارای یک پارامتر قابل تنظیم است که می‌تواند هر عدد صحیح مثبت باشد، کدهای رایس آن‌هایی هستند که پارامتر قابل تنظیم آن، عددی به صورت است. از آنجایی که کامپیوتر‌ها با منطق دودویی کار می‌کنند، این امر باعث می‌شود تا رمزگذاری رایس برای استفاده در کامپیوتر بسیار راحت باشد زیرا به راحتی می‌توان آن را در عدد 2 ضرب و تقسیم کرد. رایس بسیار علاقه‌مند بود تا این زیرمجموعه ساده‌تر را ارائه کند؛ به این دلیل که توزیع‌های هندسی اغلب با زمان تغییر می‌کنند، یا که دقیقاً شناخته شده نیستند و یا هر دو. رمزگذاری رایس به عنوان مرحله رمزگذاری آنتروپی در تعدادی از روش های فشرده سازی تصویر بدون اتلاف و فشرده سازی داده‌های صوتی استفاده می‌شود. بررسی کلی ساختار کدها رمزگذاری Golomb از یک پارامتر قابل تنظیم برای تقسیم مقدار ورودی به دو بخش استفاده می‌کند: ، نتیجه تقسیم توسط و ، باقی‌مانده. خارج قسمت در قالب رمزگذاری یگانی (unary) و به دنبال آن مقدار باقی‌مانده در رمزگذاری دودویی منقطع قرار می‌گیرد. عموماً، این دو بخش با عبارات زیر بیان می‌شوند، به طوری که عددی است که می‌بایست رمزگذاری شود: و . به طور مشخص، برای رمزگذاری رایس تنها دارای b بیت است و برای رمزگذاری Golomb بین b-1 و b بیت متغیر است (یعنی M عددی به صورت نیست). پارامتر M تابعی از فرآیند برنولی متناظر آن است، که به صورت احتمال موفقیت در یک آزمایش برنولی معین، به صورت پارامتری به شکل می‌باشد. رمزنگاری Golomb برای این توزیع معادل رمزگذاری هافمن برای احتمالات مشابه است؛ اگر این امکان وجود داشت که رمز هافمن را محاسبه کنیم. استفاده با اعداد صحیح علامت دار طرح‌واره Golomb طوری طراحی شده بود تا دنباله‌ای از اعداد غیر منفی را رمزگذاری کند. | ## بخش 2: کدگذاری گولومب | با این وجود، به راحتی می‌توان آن را با استفاده از یک طرح همپوشانی و در‌هم‌آمیزی طوری بسط داد تا برای دنباله های دارای اعداد منفی نیز آن را بپذیریم. n اُمین عدد منفی (یعنی n-) به n اُمین عدد فرد (یعنی 2n-1) و m اُمین مقدار مثبت به m اُمین عدد زوج (یعنی 2m) نگاشت می‌شود. این روند به صورت ریاضی به این صورت بیان شود: یک مقدار مثبت نگاشت شده است به ( ) و یک مقدار منفی نگاشت شده است به ( ) چنین نگاشتی ممکن است برای سادگی استفاده شود، حتی اگر بهینه‌ترین حالت ممکن نباشد. رمزهایی که برای توزیع‌های هندسی دو طرفه واقعاً بهینه باشند، شامل انواع مختلفی از رمز Golomb هستند، بسته به اینکه پارامترهای توزیع چه باشند؛ از جمله همین مورد. این رمزگذاری Rice-Golomb است، به طوری که رمز باقیمانده از رمزگذاری دودویی منقطع ساده استفاده می‌کند، که همچنین با نام "رمزگذاری رایس" نیز شناخته می‌شود (سایر رمزگذاری های با طول متغیر دودویی، مانند رمزگذاری های حسابی یا هافمن، برای رمزهای باقیمانده نیز امکان پذیر است؛ اگر توزیع آماری رمزهای باقیمانده خطی و مسطح نباشد، و خصوصاً وقتی که همه باقی‌مانده‌های ممکن بعد از تقسیم استفاده نشده باشند). در این الگوریتم، اگر پارامتر M عددی به صورت باشد، معادل ساده ای از رمزگذاری رایس می‌شود. به طور خلاصه: رمزگذاری خارج قسمتqخروجی 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 N رمزگذاری باقی مانده 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 تقسیم می‌شود و اینگونه رمزگذاری می‌شود:(لازم نیست که ویرگول جداکننده را در جریان خروجی رمزگذاری کنید، زیرا 0 در انتهای کد q برای تعیین زمانی که q به پایان می رسد و r شروع می شود کفایت می‌کند؛ هر دو رمز qcode و rcode خودمحدودکننده هستند). استفاده برای رمزگذاری به میزان زمان اجرا الفبایی شامل دو نماد یا مجموعه ای از دو رویدادِ P و Q به ترتیب با احتمال‌های p و ، به طوری که داده شده است. رمزگذاری Golomb می‌تواند برای رمزگذاری تعدادی صفر یا چند P که توسط Q های تکی از هم جدا شده استفاده شود. وقتی p = 1/2 ،M = 1 باشند و کد Golomb با یگانی مطابقت دارد ( تا P و به دنبال آن یک Q به صورت n تا یک و به دنبال آن یک صفر رمزگذاری می‌شود). اگر رمز ساده‌تر مد نظر باشد، می‌توان پارامتر در Golomb-Rice (یعنی پارامتر گولومب) را مساوی نزدیکترین عدد صحیح به قرار داد؛ اگرچه ممکن است همیشه بهترین مقدار نباشد، اما معمولاً بهترین مقدار برای Rice است و عملکرد فشرده سازی آن خیلی نزدیک به رمز گولومبِ بهینه است. (خود رایس پیشنهاد داد تا از رمزهای مختلف برای داده های یکسان استفاده شود تا بفهمیم کدام یک بهترین روش است. بعد تر، محققی از آزمایشگاه JPL روش‌های مختلفی را برای بهینه سازی یا تخمین پارامتر برای رمز ارائه داد. ) استفاده از رمز رایس با یک قسمت دودویی که بیت برای به دنباله های رمزگذاری طول اجرا به طوری که در آن P دارای احتمال باشد را در نظر بگیرید. اگر احتمال این باشد که یک بیت بخشی از یک دنباله تایی باشد ( تا P و یک Q) و نرخ فشرده سازی آن دنباله باشد، سپس نرخ فشرده سازی مورد انتظار به صورت زیر است: فشرده سازی اغلب این گونه بیان می شود: ، نسبت فشرده شده است. | ## بخش 3: کدگذاری گولومب | به عنوان مثال، با در استفاده از کد رایس، تعیین برای ، بازده برای فشرده سازی را نتیجه می‌دهد، در حالی که حد آنتروپی است. رمزگذاری گولومب-رایسِ طول اجرای انطباقی هنگامی که توزیع احتمال برای اعداد صحیح شناخته شده نیست، نمی توان پارامتر بهینه برای رمزگذار Golomb-Rice را تعیین کرد. بنابراین، در بسیاری از برنامه‌ها، از یک رویکردِ دو-گذر استفاده می‌شود: اول، بلوک داده اسکن می‌شود تا یک تابع چگالی احتمال (PDF) برای داده‌ها را تخمین بزند. یک روش جایگزین برای اینکه داده های عدد صحیح که PDF آن مشخص نیست یا متغیر است را با بازدهی بالا رمزگذاری کنیم این است از رمزگذار سازگار-برگشتی استفاده کنیم. یک رمزگشا نیز می‌تواند از همان قاعده پیروی کند تا تغییرات پارامترهای رمزگذاری را ردیابی کند، بنابراین هیچ اطلاعات جانبی بجز داده های رمزگذاری، لازم نیست که منتقل شود. با فرض یک PDF Gaussian عمومی شده، که طیف گسترده‌ای از آماری را که در داده‌هایی از قبیل خطاهای پیش‌بینی دیده می‌شود یا ضرایب تبدیل‌شده در کدک‌های چندرسانه‌ای را نشان می‌دهد، الگوریتم رمزگذاری RLGR می‌تواند در چنین برنامه هایی عملکرد بسیار خوبی داشته باشد. استفاده ها تعداد بیشماری از رمزگذارهای سیگنال‌ از رمز رایس برای باقی مانده‌های پیش بینی استفاده می‌کنند. در الگوریتم‌های پیش‌بینی، چنین باقیمانده‌هایی معمولاً در یک توزیع هندسی دو طرفه قرار می‌گیرند، در مقایسه با باقیمانده های بزرگ، باقی مانده های کوچک بیشتر از متداول هستند، و رمز رایس تخمین نزدیکی از رمز Huffman برای چنین توزیعی بدست می‌آورد با این تفاوت که سربار اینکه مجبور باشیم جدول هافمن را هم منتقل کنیم را نداریم. یک سیگنال که با هیچ توزیع هندسی‌ای مطابقت ندارد، یک موج سینوسی است، زیرا باقیمانده‌های دیفرانسیل یک سیگنال سینوسی ایجاد می‌کنند که مقادیر آن ایجاد یک توزیع هندسی نمی‌کنند (بالاترین و پایینترین مقادیر باقیمانده به طور مشابه دارای تکرار بالایی هستند، فقط مقادیر میانه مثبت و باقیمانده‌های منفی کمتر اتفاق می افتند). یکی از این آزمایش‌ها منتج به نمودار نسبت فشرده‌سازی می‌شود که در پایین آمده است. در این فشرده سازی‌ها، داده های دیفرانسیل فضای مترقی مجموعه ای متناوب از مقادیر مثبت و منفی در نزدیکی عدد 0 به دست می آورند، که به اعداد صحیح مثبت نگاشت می‌شوند (با دو برابر کردن مقدار مطلق و اضافه کردن عدد یک اگر ورودی منفی باشد) و سپس رمزگذاری رایس-گولومب با تغییر دادن مقسوم‌علیه که کوچک باقی می‌ماند، اعمال می‌شود. وسط|قاب|نسبت‌های فشرده سازی آزمایش رایس با رمزگذاری Golomb در این نتایج متوجه می‌شویم، رمزگذاری رایس ممکن است دنباله‌های بسیار طولانی از بیت 1 را برای خارج‌قسمت ایجاد کند. در عمل، اغلب لازم است که طول کل دنباله بیت‌هایی از 1، محدود شود؛ بنابراین یک نسخه اصلاح شده از رمزگذاری Rice-Golomb شامل جایگزین کردن رشته طولانی بیت 1 با رمزگذاری طول آن رشته توسط یک رمزگذاری بازگشتی رایس-گلومب است. | ## جمع‌بندی | برای انجام این کار لازم است برخی از مقادیر علاوه بر مقسوم علیه اولیه k، رزرو شوند تا تمایز لازم را ممکن‌سازد.