गोलोम्ब कोडिंग

गोलोम्ब कोडिंग 1960 के दशक में सोलोमन डब्ल्यू. गोलोम्ब द्वारा आविष्कृत डेटा संपीड़न कोड के समूह का उपयोग करके दोषरहित डेटा संपीड़न विधि है। इस प्रकार ज्यामितीय वितरण का अनुसरण करने वाले अक्षरों में इष्टतम उपसर्ग कोड के रूप में गोलोम्ब कोड होता है, गोलोम्ब कोडिंग को उन स्थितियों के लिए अत्यधिक उपयुक्त बनाना होता है जहां इनपुट स्ट्रीम में छोटे मानों की घटना बड़े मानों की तुलना में अधिक होने की संभावना है।

राइस कोडिंग

राइस कोडिंग (रॉबर्ट एफ. राइस द्वारा आविष्कार) सरल (किन्तु संभवतः उप-इष्टतम) उपसर्ग कोड का उत्पादन करने के लिए गोलोम्ब कोड के समूह के उपसमुच्चय का उपयोग करने को दर्शाता है। इस प्रकार राइस ने कोड के इस समुच्चय का उपयोग अनुकूली कोडिंग योजना में किया था; राइस कोडिंग या तो उस अनुकूली योजना को संदर्भित कर सकती है या गोलोम्ब कोड के उस उपसमुच्चय का उपयोग कर सकती है। जबकि गोलोम्ब कोड में ट्यून करने योग्य मापदंड होता है जो कोई भी धनात्मक पूर्णांक मान हो सकता है, इस प्रकार राइस कोड वे होते हैं जिनमें ट्यून करने योग्य मापदंड दो की शक्ति है। यह राइस कोड को कंप्यूटर पर उपयोग के लिए सुविधाजनक बनाता है क्योंकि 2 से गुणा और भाग को बाइनरी अंकगणित में अधिक कुशलता से प्रयुक्त किया जा सकता है।

राइस को इस सरल उपसमुच्चय को प्रस्तावित करने के लिए इस तथ्य के कारण प्रेरित किया गया था कि ज्यामितीय वितरण अधिकांशतः समय के साथ भिन्न होते हैं, इस प्रकार स्पष्ट रूप से ज्ञात नहीं होते हैं, या दोनों, इसलिए प्रतीत होता है कि इष्टतम कोड का चयन करना बहुत लाभदायक नहीं हो सकता है।

इस प्रकार राइस कोडिंग का उपयोग कई दोषरहित इमेज संपीड़न और ऑडियो डेटा संपीड़न विधियों में एन्ट्रापी एन्कोडिंग चरण के रूप में किया जाता है।

अवलोकन

मापदंड के साथ, ज्यामितीय वितरण के साथ स्रोत x के लिए गोलोम्ब कोडिंग उदाहरण p(0) = 0.2, गोलोम्ब कोड का उपयोग करते हुए M = 3. 2-बिट कोड 00 का उपयोग 20% समय किया जाता है; 3-बिट कोड 010, 011, और 100 का उपयोग 38% से अधिक समय में किया जाता है; बहुत कम मामलों में 4 बिट या अधिक की आवश्यकता होती है। इस स्रोत के लिए, एन्ट्रापी = 3.610 बिट्स; इस स्रोत के साथ इस कोड के लिए, दर = 3.639 बिट्स; इसलिए अतिरेक = 0.030 बिट्स, या दक्षता = 0.992 बिट्स प्रति बिट।

कोडों का निर्माण

गोलोम्ब कोडिंग ट्यून करने योग्य मापदंड M का उपयोग करती है इस प्रकार किसी इनपुट मान को विभाजित करने के लिए x दो भागों M, और r, शेष में q, द्वारा विभाजन का परिणाम प्राप्त करती है। भागफल को यूनरी कोडिंग में भेजा जाता है, इसके बाद शेष को संक्षिप्त बाइनरी एन्कोडिंग में भेजा जाता है। जब $M=1$, गोलोम्ब कोडिंग यूनरी कोडिंग के समान है।

गोलोम्ब-राइस कोड को ऐसे कोड के रूप में माना जा सकता है जो बिन की स्थिति के आधार पर संख्या (q) दर्शाते हैं , और इस प्रकार अन्दर ऑफसेट (r). उदाहरण चित्र स्थिति q दर्शाता है और ऑफसेट r पूर्णांक की एन्कोडिंग के लिए x गोलोम्ब-राइस मापदंड M = 3 का उपयोग करता है , ज्यामितीय वितरण के बाद स्रोत संभावनाओं के साथ p(0) = 0.2. का उपयोग किया जाता है

औपचारिक रूप से, दोनों भाग निम्नलिखित अभिव्यक्ति द्वारा दिए गए हैं, जहाँ x क्या गैर-ऋणात्मक पूर्णांक को एन्कोड किया जा रहा है:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

और

$r=x-qM$.

यह इमेज, गोलोम्ब कोड की, बिट्स में, अतिरेक को दर्शाती है Mके लिए इष्टतम रूप से चुना गया है 1 − p(0) ≥ 0.45

दोनों q और r बिट्स की परिवर्तनीय संख्याओं का उपयोग करके एन्कोड किया जाता है: इस प्रकार q यूनरी कोड द्वारा, और r द्वारा b राइस कोड के लिए बिट्स, या इनमें से कोई विकल्प b और b+1 गोलोम्ब कोड के लिए बिट्स (अर्थात्। M 2) की घात $b=\lfloor \log _{2}(M)\rfloor$ नहीं है इस प्रकार यदि $r<2^{b+1}-M$, फिर उपयोग करें b एन्कोड करने के लिए बिट्स r; अन्यथा, b+1 उपयोग करें बिट एन्कोड करने के लिए r. स्पष्ट रूप से, $b=\log _{2}(M)$ यदि M 2 की घात है और हम इसके सभी मानों r साथ b बिट्स को एन्कोड कर सकते हैं.

पूर्णांक x गोलोम्ब द्वारा उपचारित बर्नौली प्रक्रिया की रन लंबाई थी, जिसका ज्यामितीय वितरण 0 से प्रारंभ होता है। इस प्रकार मापदंड का सबसे अच्छा विकल्प M संगत बर्नौली प्रक्रिया का फलन है, जिसे मापदंडाइज़ $p=P(x=0)$ किया गया है किसी दिए गए बर्नौली परीक्षण में सफलता की संभावना M या तो वितरण का माध्यिका है या माध्यिका ±1 इसे इन असमानताओं द्वारा निर्धारित किया जा सकता है:

$(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$

जिनका समाधान किया जाता है

$M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil$.

उदाहरण के लिए p(0) = 0.2:

$M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3$.

इस वितरण के लिए गोलोम्ब कोड समान संभावनाओं के लिए हफ़मैन कोड के समान है, यदि स्रोत मानों के अनंत समुच्चय के लिए हफ़मैन कोड की गणना करना संभव हो जाता है।

हस्ताक्षरित पूर्णांकों के साथ प्रयोग करें

गोलोम्ब की योजना गैर-ऋणात्मक संख्याओं के अनुक्रमों को एन्कोड करने के लिए डिज़ाइन की गई थी। चूँकि, इसे ओवरलैप और इंटरलीव योजना का उपयोग करके ऋणात्मक संख्याओं वाले अनुक्रमों को स्वीकार करने के लिए सरलता से बढ़ाया जाता है, इस प्रकार जिसमें सभी मानों को अद्वितीय और प्रतिवर्ती विधि से कुछ धनात्मक संख्या में पुन: असाइन किया जाता है। अनुक्रम प्रारंभ होता है: 0, −1, 1, −2, 2, −3, 3, −4, 4... n-वां ऋणात्मक मान (अर्थात, $-n$) को n पर मैप किया गया है विषम संख्या ($2n-1$), और उन्हें धनात्मक मान को m-वें सम संख्या ($2m$) में मैप किया जाता है . इसे गणितीय रूप से इस प्रकार व्यक्त किया जा सकता है: धनात्मक मान x को मैप ($x'=2|x|=2x,\ x\geq 0$) किया गया है , और ऋणात्मक मान y को मैप ($y'=2|y|-1=-2y-1,\ y<0$) किया गया है इस प्रकार के कोड का उपयोग सरलता के लिए किया जा सकता है, तथापि यह उप-इष्टतम हो वास्तव में दो-तरफा ज्यामितीय वितरण के लिए इष्टतम कोड में इस सहित वितरण मापदंडों के आधार पर गोलोम्ब कोड के कई प्रकार सम्मिलित हैं।

सरल एल्गोरिथ्म

नीचे राइस-गोलोम्ब एन्कोडिंग है, जहां शेष कोड सरल ट्रंकेटेड बाइनरी एन्कोडिंग का उपयोग करता है, जिसे राइस कोडिंग भी कहा जाता है (अन्य अलग-अलग लंबाई वाली बाइनरी एन्कोडिंग, जैसे अंकगणित या हफमैन एन्कोडिंग, शेष कोड के लिए संभव हैं, यदि शेष कोड का सांख्यिकीय वितरण होता है) समतल नहीं है, और इस प्रकार विशेष रूप से तब जब विभाजन के बाद सभी संभावित शेषफलों का उपयोग नहीं किया जाता है)। इस एल्गोरिदम में, यदि m मापदंड 2 की शक्ति है, तो यह सरल राइस एन्कोडिंग के समान हो जाता है:

1. मापदंड M को पूर्णांक मान पर ठीक करें।
2. N के लिए, एन्कोड किया जाने वाला नंबर खोजे
   1. भागफल = q = फ्लोर(n/m)
   2. शेष = r = n मोडुलो m
3. कोडवर्ड जेनरेट करें
   1. कोड प्रारूप: <कोटिएंट कोड><शेष कोड>, जहाँ
   2. कोटिएंट कोड (यूनरी कोडिंग में)
      1. 1 बिट्स की q-लंबाई स्ट्रिंग लिखें (वैकल्पिक रूप से, 0 बिट्स की)
      2. 0 बिट लिखें (क्रमशः, 1 बिट)
   3. शेष कोड (काटे गए बाइनरी एन्कोडिंग में)
      1. माना $b=\lfloor \log _{2}(M)\rfloor$
         1. यदि $r<2^{b+1}-M$ b बिट्स का उपयोग करके बाइनरी प्रतिनिधित्व में कोड r।
         2. यदि $r\geq 2^{b+1}-M$ नंबर कोड करें $r+2^{b+1}-M$ b + 1 बिट्स का उपयोग करके बाइनरी प्रतिनिधित्व में।

डिकोडिंग:

1. q के एकल प्रतिनिधित्व को डिकोड करें (कोड की प्रारंभ में 1 की संख्या गिनें)
2. 0 सीमांकक छोड़ें
3. माना $b=\lfloor \log _{2}(M)\rfloor$
   1. अगले b बिट्स को बाइनरी नंबर r' के रूप में समझें। यदि