Fibonacci coding
ریاضی اور کمپیوٹنگ میں، فبونیکی کوڈنگ ایک عالمگیر کوڈ ہے جو مثبت عدد کو بائنری کوڈ کے الفاظ میں انکوڈ کرتا ہے۔ یہ فبونیکی نمبروں پر مبنی انٹیجرز کی نمائندگی کی ایک مثال ہے۔ ہر کوڈ لفظ "11" کے ساتھ ختم ہوتا ہے اور اختتام سے پہلے "11" کی کوئی دوسری مثال نہیں رکھتا ہے۔ فبونیکی کوڈ کا زیکنڈورف کی نمائندگی سے گہرا تعلق ہے، ایک پوزیشنل عددی نظام جو زیکنڈورف کے نظریہ کو استعمال کرتا ہے اور اس کی خاصیت یہ ہے کہ کسی بھی نمبر کی نمائندگی مسلسل 1s کے ساتھ نہیں ہوتی ہے۔ کسی خاص عدد کے لیے فبونیکی کوڈ لفظ بالکل عدد کی زیکنڈورف نمائندگی ہے جس کے ہندسوں کی ترتیب الٹی ہوتی ہے اور آخر میں ایک اضافی "1" منسلک ہوتا ہے۔ تعریف کسی نمبر کے لیے، اگر کوڈ لفظ کے ہندسوں کی نمائندگی کرتا ہے تو ہمارے پاس: واں فبونیکی نمبر کہاں ہے، اور اسی طرح واں الگ فبونیکی نمبر کہاں سے شروع ہوتا ہے۔ آخری بٹ ہمیشہ 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، کے طور پر انکوڈ کیے گئے ہیں۔ اس صورت میں، سٹرنگ کی لمبائی کے فنکشن کے طور پر انکوڈنگ کی تعداد ٹربونیکی نمبروں کی ترتیب سے دی جاتی ہے۔ کسی دی گئی علامت کے بعد کن علامتوں کی اجازت ہے اس کی وضاحت کرنے والی عمومی رکاوٹوں کے لیے، زیادہ سے زیادہ معلومات کی شرح پہلے زیادہ سے زیادہ اینٹروپی رینڈم واک کا استعمال کرتے ہوئے زیادہ سے زیادہ منتقلی کے امکانات کو تلاش کرکے حاصل کی جا سکتی ہے، پھر کسی پیغام کو انکوڈ کرنے کے لیے اینٹروپی کوڈر (ڈیکوڈر کے ساتھ تبدیل شدہ انکوڈر کے ساتھ) کا استعمال کریں جو علامتوں کی ترتیب کے طور پر پایا گیا زیادہ سے زیادہ منتقلی کے امکانات کو پورا کرتا ہے۔ گولڈن ریشو بیس نیگا فبونیکی کوڈنگ آسٹرووسکی عدد یونیورسل کوڈ ویریکوڈ، ایک عملی ایپلی کیشن زیکینڈورف تھیوریم زیادہ سے زیادہ اینٹروپی بے ترتیب واک حوالہ جات مزید پڑھنا غیر معیاری پوزیشنل عددی نظام لاس لیس کمپریشن الگورتھم فبونیکی نمبر