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

गोलोम्ब कोडिंग 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' के रूप में समझें। यदि $r'<2^{b+1}-M$ रखता है, फिर अनुस्मारक $r=r'$ है
   2. अन्यथा b + 1 बिट्स को बाइनरी नंबर r' के रूप में समझें, अनुस्मारक $r=r'-2^{b+1}+M$ द्वारा दिया गया है
4. गणना करें $N=q*M+r$

उदाहरण

समुच्चय M = 10. इस प्रकार $b=\lfloor \log _{2}(10)\rfloor =3$. कटऑफ है $2^{b+1}-M=16-10=6$.

भागफल भाग का एन्कोडिंग q आउटपुट बिट्स 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 $\vdots$ $\vdots$ N $\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

उदाहरण के लिए, मापदंड का उपयोग करके राइस-गोलोम्ब एन्कोडिंग के साथ M = 10, दशमलव संख्या 42 को पहले विभाजित किया जाएगा q=4 और r = 2, और qcode के रूप में एन्कोड किया जाएगा(q),rकोड(r) = qcode(4),rcode(2) = 11110,010 (आपको आउटपुट स्ट्रीम में अलग करने वाले अल्पविराम को एनकोड करने की आवश्यकता नहीं है, क्योंकि के अंत में 0 है q कोड कब कहने के लिए पर्याप्त है q समाप्त होता है और r प्रारंभ करना ; qकोड और rकोड दोनों स्व-सीमांकित हैं)।

रन-लेंथ एन्कोडिंग के लिए उपयोग करें

ध्यान दें कि p और 1 – p पिछले अनुभागों में उपयोग की तुलना में इस अनुभाग में उलट दिया गया है।

दो प्रतीकों की वर्णमाला, या दो घटनाओं, पी और q का समुच्चय, संभावनाओं के साथ पी और (1 − p) क्रमशः, कहाँ p ≥ 1/2, गोलोम्ब कोडिंग का उपयोग एकल Q′s द्वारा अलग किए गए शून्य या अधिक P′s के रन को एन्कोड करने के लिए किया जा सकता है। इस एप्लिकेशन में, मापदंड m की सबसे अच्छी सेटिंग निकटतम पूर्णांक है $-{\frac {1}{\log _{2}p}}$. जब पी = 1/2, m = 1, और गोलोम्ब कोड यूनरी से मेल खाता है (n ≥ 0 P′s के बाद Q आता है, इसे n के रूप में एन्कोड किया जाता है जिसके बाद शून्य आता है)। यदि सरल कोड वांछित है, तो कोई गोलोम्ब-राइस मापदंड निर्दिष्ट कर सकता है b (अर्थात, गोलोम्ब मापदंड $M=2^{b}$) के निकटतम पूर्णांक तक $-\log _{2}(-\log _{2}p)$; चूँकि यह हमेशा सबसे अच्छा मापदंड नहीं होता है, यह आमतौर पर सबसे अच्छा राइस मापदंड होता है और इसका संपीड़न प्रदर्शन इष्टतम गोलोम्ब कोड के काफी करीब होता है। (राइस ने स्वयं ही डेटा के लिए विभिन्न कोड का उपयोग करने का प्रस्ताव दिया ताकि यह पता लगाया जा सके कि कौन सा सबसे अच्छा था। बाद में जेट प्रोपल्शन प्रयोगशाला के शोधकर्ता ने कोड मापदंड को अनुकूलित करने या अनुमान लगाने के विभिन्न तरीकों का प्रस्ताव दिया।)

बाइनरी भाग वाले राइस कोड का उपयोग करने पर विचार करें b बिट्स रन-लेंथ एन्कोड अनुक्रमों के लिए जहां पी की संभावना है p. यदि $\mathbb {P} [{\text{bit is part of }}k{\text{-run}}]$ संभावना है कि बिट का हिस्सा होगा k-बिट रन ($k-1$ पीएस और q) और $({\text{compression ratio of }}k{\text{-run}})$ उस रन का संपीड़न अनुपात है, तो अपेक्षित संपीड़न अनुपात है

${\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-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}}$

संपीड़न को अधिकांशतः के रूप में व्यक्त किया जाता है $1-\mathbb {E} [{\text{compression ratio}}]$, अनुपात संकुचित। के लिए $p\approx 1$, रन-लेंथ कोडिंग दृष्टिकोण के परिणामस्वरूप एन्ट्रॉपी (सूचना सिद्धांत) के करीब संपीड़न अनुपात होता है। उदाहरण के लिए, राइस कोड का उपयोग करना $b=6$ के लिए $p=0.99$ पैदावार 91.89% संपीड़न, जबकि एन्ट्रापी सीमा है 91.92%.

अनुकूली रन-लंबाई गोलोम्ब-राइस एन्कोडिंग

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

पूर्णांक डेटा को कुशलतापूर्वक एनकोड करने के लिए वैकल्पिक तरीका जिसका पीडीएफ ज्ञात नहीं है, या भिन्न हो रहा है, बैकवर्ड-अनुकूली एनकोडर का उपयोग करना है। run-length Golomb-Rice (RLGR) कोड बहुत ही सरल एल्गोरिदम का उपयोग करके इसे प्राप्त करता है जो Golomb-Rice मापदंड को ऊपर या नीचे समायोजित करता है, जो निर्भर करता है अंतिम एन्कोडेड प्रतीक. डिकोडर एन्कोडिंग मापदंडों की भिन्नता को ट्रैक करने के लिए उसी नियम का पालन कर सकता है, इसलिए किसी भी अतिरिक्त जानकारी को प्रसारित करने की आवश्यकता नहीं है, केवल एन्कोडेड डेटा। सामान्यीकृत गॉसियन पीडीएफ को मानते हुए, जो डेटा में देखे गए आंकड़ों की विस्तृत श्रृंखला को कवर करता है जैसे कि भविष्यवाणी त्रुटियां या मल्टीमीडिया कोडेक्स में गुणांक बदलना, rएलजीr एन्कोडिंग एल्गोरिदम ऐसे अनुप्रयोगों में बहुत अच्छा प्रदर्शन कर सकता है।

अनुप्रयोग

गोलोम्ब-कोडित राइस एल्गोरिदम प्रयोग संपीड़न अनुपात

कई सिग्नल कोडेक्स भविष्यवाणी अवशेषों के लिए राइस कोड का उपयोग करते हैं।

भविष्य कहनेवाला एल्गोरिदम में, ऐसे अवशेष दो-तरफा ज्यामितीय वितरण में आते हैं, जिसमें छोटे अवशेष बड़े अवशेषों की तुलना में अधिक बार होते हैं, और राइस कोड हफ़मैन तालिका को प्रसारित करने के ओवरहेड के बिना इस तरह के वितरण के लिए हफ़मैन कोड का बारीकी से अनुमान लगाता है। . एक संकेत जो ज्यामितीय वितरण से मेल नहीं खाता है वह साइन तरंग है, क्योंकि विभेदक अवशेष साइनसॉइडल सिग्नल बनाते हैं जिनके मान ज्यामितीय वितरण नहीं बना रहे हैं (उच्चतम और निम्नतम अवशेष मूल्यों में घटनाओं की समान उच्च आवृत्ति होती है, केवल औसत धनात्मक और ऋणात्मक होता है) अवशेष कम बार मिलते हैं)।

कई दोषरहित ऑडियो डेटा संपीड़न, जैसे शॉर्टन (फ़ाइल प्रारूप), एफएलएसी, Apple लॉसलेस, और MPEG-4 ALS, रैखिक भविष्य कहनेवाला कोडिंग (Apple लॉसलेस में एडाप्टिव FIR फ़िल्टर कहा जाता है) के बाद राइस कोड का उपयोग करते हैं। राइस कोडिंग का उपयोग FELICS दोषरहित छवि कोडेक में भी किया जाता है।

गोलोम्ब-राइस कोडर का उपयोग राइस एल्गोरिथ्म आधारित दोषरहित छवि कोडेक्स के एन्ट्रापी कोडिंग चरण में किया जाता है। ऐसा ही प्रयोग दिखाया गया संपीड़न अनुपात ग्राफ़ उत्पन्न करता है।

दोषरहित JPEG#JPEG-LS|JPEG-LS योजना पूर्वानुमान अवशेषों को एनकोड करने के लिए राइस-गोलोम्ब का उपयोग करती है।

run-length Golomb–Rice (RLGR) Golomb-Rice कोडिंग का ऊपर उल्लिखित अनुकूली संस्करण, वर्चुअल मशीनों में स्क्रीन सामग्री को एन्कोड करने के लिए उपयोग किया जाता है। माइक्रोसॉफ्ट रिमोट डेस्कटॉप प्रोटोकॉल का रिमोटएफएक्स घटक।

यह भी देखें

• इलियास डेल्टा कोडिंग

अग्रिम पठन

• Golomb, Solomon W. (1966). Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data". IEEE Transactions on Communications. 16 (9): 889–897. doi:10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979), , "Some Practical Universal Noiseless Coding Techniques", Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, March 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
• David Salomon. "Data Compression",ISBN 0-387-95045-1.
• H. S. Malvar, Adaptive run-length/Golomb–Rice encoding of quantized generalized Gaussian sources with unknown statistics, Proc. Data Compression Conference, 2006.
• RLGR Entropy Encoding, Microsoft MS-RDPRFX Open Specification, RemoteFX codec for Remote Desktop Protocol.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines Archived 2020-10-05 at the Wayback Machine. MIT Press, Cambridge MA, 2010.