Fibonacci coding
গণিত এবং কম্পিউটিং-এ, ফিবোনাচ্চি কোডিং একটি সার্বজনীন কোড যা ধনাত্মক পূর্ণসংখ্যাকে বাইনারি কোড শব্দের মধ্যে এনকোড করে। এটি ফিবোনাচ্চি সংখ্যার উপর ভিত্তি করে পূর্ণসংখ্যার উপস্থাপনার একটি উদাহরণ। প্রতিটি কোড শব্দ "11" দিয়ে শেষ হয় এবং শেষের আগে "11" এর অন্য কোনও দৃষ্টান্ত থাকে না। ফিবোনাচ্চি কোডটি জেকেনডর্ফ উপস্থাপনার সাথে ঘনিষ্ঠভাবে সম্পর্কিত, একটি অবস্থানগত সংখ্যা পদ্ধতি যা জেকেনডর্ফের উপপাদ্য ব্যবহার করে এবং এর বৈশিষ্ট্য রয়েছে যে কোনও সংখ্যার পরপর 1s এর প্রতিনিধিত্ব নেই। একটি নির্দিষ্ট পূর্ণসংখ্যার জন্য ফিবোনাচ্চি কোড শব্দটি ঠিক পূর্ণসংখ্যার জেকেনডর্ফ উপস্থাপনা যার সংখ্যার ক্রম বিপরীত এবং শেষে একটি অতিরিক্ত "1" সংযুক্ত থাকে। সংজ্ঞা একটি সংখ্যার জন্য, যদি কোড শব্দের অঙ্কগুলি প্রতিনিধিত্ব করে তবে আমাদের কাছে রয়েছেঃ যেখানে তম ফিবোনাচ্চি সংখ্যাটি রয়েছে, এবং তাই দশম স্বতন্ত্র ফিবোনাচ্চি সংখ্যাটি দিয়ে শুরু হয়। শেষ বিটটি সর্বদা 1 এর একটি সংযুক্ত বিট এবং স্থান মান বহন করে না। এটি দেখানো যেতে পারে যে এই ধরনের কোডিং অনন্য, এবং যে কোনও কোড শব্দে "11"-এর একমাত্র উপস্থিতি হল শেষে অর্থাৎ। d (k − 1) এবং d (k)। উপান্তীয় বিটটি সবচেয়ে গুরুত্বপূর্ণ বিট এবং প্রথম বিটটি সবচেয়ে কম গুরুত্বপূর্ণ বিট। এছাড়াও অগ্রবর্তী শূন্যগুলি বাদ দেওয়া যায় না যেমন উদাহরণস্বরূপ। দশমিক সংখ্যা। প্রথম কয়েকটি ফিবোনাচ্চি কোড নীচে দেখানো হয়েছে, এবং তাদের তথাকথিত অন্তর্নিহিত সম্ভাবনা, প্রতিটি সংখ্যার মান যার ফিবোনাচ্চি কোডিংয়ে ন্যূনতম আকারের কোড রয়েছে। একটি পূর্ণসংখ্যা এন-কে এনকোড করতেঃ এন-এর সমান বা তার চেয়ে কম বৃহত্তম ফিবোনাচ্চি সংখ্যাটি খুঁজে বের করুন; অবশিষ্টাংশের উপর নজর রেখে এন থেকে এই সংখ্যাটি বিয়োগ করুন। যদি বিয়োগ করা সংখ্যাটি 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, হিসাবে এনকোড করা হয়েছে। এই ক্ষেত্রে, স্ট্রিং দৈর্ঘ্যের ফাংশন হিসাবে এনকোডিংয়ের সংখ্যা ট্রাইবোনাচ্চি সংখ্যার ক্রম দ্বারা দেওয়া হয়। একটি প্রদত্ত প্রতীকের পরে কোন প্রতীকগুলি অনুমোদিত তা সংজ্ঞায়িত করার জন্য, সর্বাধিক তথ্যের হার প্রথমে সর্বাধিক এনট্রপি র্যান্ডম ওয়াক ব্যবহার করে সর্বোত্তম রূপান্তর সম্ভাব্যতা খুঁজে বের করে প্রাপ্ত করা যেতে পারে, তারপরে একটি বার্তা এনকোড করতে এনট্রপি কোডার (ডিকোডারের সাথে সুইচড এনকোডার সহ) ব্যবহার করা যেতে পারে। আরও দেখুন গোল্ডেন রেশিও বেস নেগাফিবোনাচ্চি কোডিং অস্ট্রোস্কি সংখ্যা সার্বজনীন কোড ভেরিকোড, একটি ব্যবহারিক প্রয়োগ জেকেনডর্ফের উপপাদ্য সর্বাধিক এনট্রপি র্যান্ডম ওয়াক রেফারেন্স আরও পড়া অ-মানক অবস্থানগত সংখ্যা সিস্টেম লসলেস কম্প্রেশন অ্যালগরিদম ফিবোনাচি সংখ্যা