Fibonacci coding
ગણિત અને કમ્પ્યુટિંગમાં, ફિબોનાકી કોડિંગ એ એક સાર્વત્રિક કોડ છે જે હકારાત્મક પૂર્ણાંકોને દ્વિસંગી કોડ શબ્દોમાં એન્કોડ કરે છે. તે ફિબોનાકી સંખ્યાઓ પર આધારિત પૂર્ણાંકોની રજૂઆતનું એક ઉદાહરણ છે. દરેક કોડ શબ્દ "11" સાથે સમાપ્ત થાય છે અને અંત પહેલા "11" ના અન્ય કોઈ ઉદાહરણો નથી. ફિબોનાકી કોડ ઝેકેન્ડોર્ફ પ્રતિનિધિત્વ સાથે નજીકથી સંબંધિત છે, જે એક સ્થાયી અંક પ્રણાલી છે જે ઝેકેન્ડોર્ફના પ્રમેયનો ઉપયોગ કરે છે અને તેમાં એવો ગુણધર્મ છે કે કોઈ પણ સંખ્યા સતત 1s સાથે પ્રતિનિધિત્વ કરતી નથી. ચોક્કસ પૂર્ણાંક માટે ફિબોનાકી કોડ શબ્દ બરાબર પૂર્ણાંકની ઝેકેન્ડોર્ફ રજૂઆત છે, જેમાં તેના અંકોના ક્રમને ઉલટાવી દેવામાં આવે છે અને અંતે એક વધારાનું "1" જોડવામાં આવે છે. વ્યાખ્યા સંખ્યા માટે, જો પ્રતિનિધિત્વ કરતા કોડ શબ્દના અંકોનું પ્રતિનિધિત્વ કરે છે, તો આપણી પાસે છેઃ ક્યાં છે th ફિબોનાકી નંબર, અને તે જ રીતે th અલગ ફિબોનાકી નંબર શરૂ થાય છે. છેલ્લો બીટ હંમેશા 1 નો જોડાયેલો બીટ હોય છે અને તે સ્થાન મૂલ્ય ધરાવતો નથી. તે દર્શાવી શકાય છે કે આવા કોડિંગ અનન્ય છે, અને કોઈપણ કોડ શબ્દમાં "11" ની એકમાત્ર ઘટના અંતે છે એટલે કે. d (k − 1) અને d (k). ઉપાંત્ય બીટ સૌથી નોંધપાત્ર બીટ છે અને પ્રથમ બીટ સૌથી ઓછી નોંધપાત્ર બીટ છે. ઉપરાંત અગ્રણી શૂન્યને અવગણવામાં નહીં આવે, જેમ કે તેઓ કરી શકે છે. દશાંશ સંખ્યાઓ. પ્રથમ થોડા ફિબોનાકી કોડ્સ નીચે દર્શાવવામાં આવ્યા છે, અને તેમની કહેવાતી ગર્ભિત સંભાવના પણ, ફિબોનાકી કોડિંગમાં લઘુતમ કદના કોડ ધરાવતી દરેક સંખ્યાનું મૂલ્ય. પૂર્ણાંક N ને એન્કોડ કરવા માટેઃ N ની બરાબર અથવા તેનાથી ઓછી સૌથી મોટી ફિબોનાકી સંખ્યા શોધો; બાકીની સંખ્યાને ધ્યાનમાં રાખીને આ સંખ્યાને N માંથી બાદ કરો. જો બાદ કરવામાં આવેલી સંખ્યા ith ફિબોનાકી સંખ્યા F (i) હોય, તો કોડ શબ્દમાં i-2ની જગ્યાએ 1 મૂકો (સ્થાન 0 તરીકે સૌથી ડાબી બાજુના અંકની ગણતરી કરો). અગાઉના પગલાંઓનું પુનરાવર્તન કરો, બાકીના N ને બદલીને, જ્યાં સુધી બાકીના 0 સુધી પહોંચી ન જાય. કોડ વર્ડમાં સૌથી જમણા અંક પછી વધારાનો 1 મૂકો. કોડ શબ્દને ડીકોડ કરવા માટે, અંતિમ "1" ને દૂર કરો, કોડ શબ્દના બિટ્સને બાકીની કિંમતો 1,2,3,5,8,13. (ફિબોનાકી સંખ્યાઓ) સોંપો અને "1" બિટ્સના મૂલ્યોનો સરવાળો કરો. અન્ય સાર્વત્રિક કોડ્સ સાથે સરખામણી ફિબોનાકી કોડિંગમાં એક ઉપયોગી ગુણધર્મ છે જે કેટલીકવાર તેને અન્ય સાર્વત્રિક કોડ્સની તુલનામાં આકર્ષક બનાવે છેઃ તે સ્વ-સમન્વયિત કોડનું ઉદાહરણ છે, જે ક્ષતિગ્રસ્ત પ્રવાહમાંથી ડેટા પુનઃપ્રાપ્ત કરવાનું સરળ બનાવે છે. મોટાભાગના અન્ય સાર્વત્રિક કોડ્સ સાથે, જો એક બીટમાં ફેરફાર કરવામાં આવે, તો તે પછી આવતા કોઈપણ ડેટાને યોગ્ય રીતે વાંચવામાં આવશે નહીં. બીજી બાજુ, ફિબોનાકી કોડિંગ સાથે, બદલાયેલ બીટ એક ટોકનને બે તરીકે વાંચવાનું કારણ બની શકે છે, અથવા બે ટોકન્સને એક તરીકે ખોટી રીતે વાંચવાનું કારણ બની શકે છે, પરંતુ સ્ટ્રીમમાંથી "0" વાંચવાથી ભૂલો આગળ ફેલાતી અટકશે. એકમાત્ર પ્રવાહ જેમાં "0" નથી તે "11" ટોકનનો પ્રવાહ હોવાથી, એક બીટ ભૂલથી ક્ષતિગ્રસ્ત પ્રવાહ અને મૂળ પ્રવાહ વચ્ચેનું કુલ સંપાદન અંતર વધુમાં વધુ ત્રણ છે. આ અભિગમ-પ્રતીકોના ક્રમનો ઉપયોગ કરીને એન્કોડિંગ, જેમાં કેટલીક પેટર્ન (જેમ કે "11") પ્રતિબંધિત છે, તેને મુક્તપણે સામાન્યીકૃત કરી શકાય છે. ઉદાહરણ નીચેનું કોષ્ટક દર્શાવે છે કે 65 નંબરને ફિબોનાકી કોડિંગમાં 0100100011 તરીકે રજૂ કરવામાં આવ્યો છે. પ્રથમ બે ફિબોનાકી સંખ્યાઓ (0 અને 1) નો ઉપયોગ થતો નથી, અને વધારાના 1 હંમેશા ઉમેરવામાં આવે છે. સામાન્યીકરણ હકારાત્મક પૂર્ણાંકો માટે ફિબોનાકી સંકેતલિપી દ્વિસંગી શબ્દમાળાઓ છે જે "11" સાથે સમાપ્ત થાય છે અને તેમાં "11" ના અન્ય કોઈ ઉદાહરણો નથી. આને દ્વિસંગી શબ્દમાળાઓમાં સામાન્યીકૃત કરી શકાય છે જે N સળંગ 1 સાથે સમાપ્ત થાય છે અને તેમાં N સળંગ 1 ના અન્ય કોઈ ઉદાહરણો નથી. દાખલા તરીકે, N = 3 માટે હકારાત્મક પૂર્ણાંકો 111,0111,00111,10111,000111,100111,010111,110111,0000111,1000111,0100111, તરીકે એન્કોડ કરવામાં આવ્યા છે. આ કિસ્સામાં, સ્ટ્રિંગ લંબાઈના કાર્ય તરીકે એન્કોડિંગની સંખ્યા ટ્રિબોનાકી સંખ્યાઓના ક્રમ દ્વારા આપવામાં આવે છે. આપેલ પ્રતીક પછી કયા પ્રતીકોને મંજૂરી આપવામાં આવે છે તે વ્યાખ્યાયિત કરતી સામાન્ય અવરોધો માટે, મહત્તમ માહિતી દર પ્રથમ મહત્તમ એન્ટ્રોપી રેન્ડમ વોકનો ઉપયોગ કરીને શ્રેષ્ઠ સંક્રમણ સંભાવનાઓ શોધીને મેળવી શકાય છે, પછી એન્ટ્રોપી કોડર (ડીકોડર સાથે સ્વિચ એન્કોડર સાથે) નો ઉપયોગ કરીને સંદેશને એન્કોડ કરવા માટે મળી આવેલી શ્રેષ્ઠ સંક્રમણ સંભાવનાઓને પરિપૂર્ણ કરતા પ્રતીકોના ક્રમ તરીકે. ગોલ્ડન રેશિયો બેઝ નેગાફિબોનાકી કોડિંગ ઓસ્ટ્રોવસ્કી નંબર યુનિવર્સલ કોડ વેરિકોડ, એક વ્યવહારુ એપ્લિકેશન ઝેકેન્ડોર્ફની થીયરમ મેક્સિમલ એન્ટ્રોપી રેન્ડમ વોક રેફરન્સ વધુ વાંચન નોન-સ્ટાન્ડર્ડ પોઝિશનલ આંકડાકીય સિસ્ટમો લોસલેસ કમ્પ્રેશન અલ્ગોરિધમ્સ ફિબોનાકી નંબરો