ترميز فيبوناتشي

في الرياضيات والحوسبة، يُعد ترميز فيبوناتشي ترميزًا عالميًا ^{[ 1 ]} يُستخدم لترميز الأعداد الصحيحة الموجبة إلى كلمات ثنائية. وهو مثال على تمثيل الأعداد الصحيحة باستخدام أعداد فيبوناتشي . تنتهي كل كلمة من كلمات الترميز بالرقم "11" ولا تحتوي على أي تكرار آخر للرقم "11" قبل نهايتها.

يرتبط رمز فيبوناتشي ارتباطًا وثيقًا بتمثيل زيكندورف ، وهو نظام عددي موضعي يستخدم نظرية زيكندورف، ويتميز بخاصية عدم وجود أي عدد له تمثيل برقمين متتاليين يساوي 1. كلمة رمز فيبوناتشي لعدد صحيح معين هي تمثيل زيكندورف الخاص بذلك العدد مع عكس ترتيب أرقامه وإضافة الرقم "1" في النهاية.

لعدد${\displaystyle N\!}$، لو${\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}$تمثل أرقام كلمة السر التي تمثل${\displaystyle N\!}$ثم لدينا:

${\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ و }}d(k-1)=d(k)=1.\!}$

حيث F ( i ) هو العدد i من متتالية فيبوناتشي ، وبالتالي فإن F ( i +2) هو العدد i المميز من متتالية فيبوناتشي الذي يبدأ بـ${\displaystyle 1,2,3,5,8,13,\ldots }$الجزء الأخير${\displaystyle d(k)}$دائماً ما يكون بتًا ملحقًا بقيمة 1 ولا يحمل قيمة مكانية.

يمكن إثبات أن هذا الترميز فريد، وأن ظهور الرقم "11" في أي كلمة ترميزية يكون في النهاية فقط (أي في d ( k - 1) و d ( k )). البت قبل الأخير هو البت الأكثر أهمية، والبت الأول هو البت الأقل أهمية. كما لا يمكن حذف الأصفار البادئة كما هو الحال في الأعداد العشرية، على سبيل المثال.

يتم عرض رموز فيبوناتشي القليلة الأولى أدناه، وكذلك ما يسمى باحتمالها الضمني ، وهي القيمة لكل رقم له رمز ذو حجم أدنى في ترميز فيبوناتشي.

رمز	تمثيل فيبوناتشي	كلمة سر فيبوناتشي	الاحتمال الضمني
1	${\displaystyle F(2)}$	11	1/4
2	${\displaystyle F(3)}$	011	1/8
3	${\displaystyle F(4)}$	0011	1/16
4	${\displaystyle F(2)+F(4)}$	1011	1/16
5	${\displaystyle F(5)}$	٠٠٠١١	1/32
6	${\displaystyle F(2)+F(5)}$	10011	1/32
7	${\displaystyle F(3)+F(5)}$	01011	1/32
8	${\displaystyle F(6)}$	000011	1/64
9	${\displaystyle F(2)+F(6)}$	100011	1/64
10	${\displaystyle F(3)+F(6)}$	010011	1/64
11	${\displaystyle F(4)+F(6)}$	001011	1/64
12	${\displaystyle F(2)+F(4)+F(6)}$	101011	1/64
13	${\displaystyle F(7)}$	0000011	1/128
14	${\displaystyle F(2)+F(7)}$	1000011	1/128

لترميز عدد صحيح N :

1. أوجد أكبر عدد فيبوناتشي يساوي أو يقل عن N ؛ اطرح هذا العدد من N ، مع الاحتفاظ بالباقي.
2. إذا كان الرقم المطروح هو رقم فيبوناتشي رقم i F ( i ) ، فضع 1 في المكان i − 2 في كلمة الشفرة (مع اعتبار الرقم الموجود في أقصى اليسار مكانًا 0).
3. كرر الخطوات السابقة، مع استبدال الباقي بـ N ، حتى يتم الوصول إلى باقي يساوي 0.
4. ضع الرقم 1 إضافياً بعد الرقم الموجود في أقصى اليمين في كلمة السر.

لفك تشفير كلمة رمزية، قم بإزالة الرقم "1" الأخير، وقم بتعيين القيم المتبقية 1،2،3،5،8،13... ( أرقام فيبوناتشي ) للبتات الموجودة في الكلمة الرمزية، وقم بجمع قيم البتات "1".

تتميز ترميز فيبوناتشي بخاصية مفيدة تجعله جذابًا أحيانًا مقارنةً برموز الترميز العالمية الأخرى: فهو مثال على الترميز ذاتي التزامن ، مما يُسهّل استعادة البيانات من تدفق بيانات تالف. في معظم رموز الترميز العالمية الأخرى، إذا تم تغيير بت واحد ، فلن تُقرأ أي من البيانات التي تليه بشكل صحيح. أما في ترميز فيبوناتشي، فقد يتسبب تغيير البت في قراءة رمز واحد على أنه اثنان، أو قراءة رمزين بشكل خاطئ على أنهما واحد، ولكن قراءة "0" من تدفق البيانات ستوقف انتشار الأخطاء. وبما أن تدفق البيانات الوحيد الذي لا يحتوي على "0" هو تدفق مكون من "11" رمزًا، فإن إجمالي مسافة التحرير بين تدفق بيانات تالف بسبب خطأ في بت واحد وتدفق البيانات الأصلي لا يتجاوز ثلاثة.

يمكن تعميم هذا النهج، الذي يعتمد على التشفير باستخدام سلسلة من الرموز، حيث تُحظر بعض الأنماط (مثل "11")، بحرية. ^{[ 2 ]}

يوضح الجدول التالي أن العدد 65 يُمثَّل في ترميز فيبوناتشي على النحو التالي: 0100100011، لأن 65 = 2 + 8 + 55. لا يُستخدم أول عددين في متتالية فيبوناتشي (0 و1)، ويُضاف دائمًا 1.

$\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{إضافي}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}$

تُمثل ترميزات فيبوناتشي للأعداد الصحيحة الموجبة سلاسل ثنائية تنتهي بالرقم "11" ولا تحتوي على أي تكرار آخر له. ويمكن تعميم ذلك على السلاسل الثنائية التي تنتهي بـ N من الآحاد المتتالية ولا تحتوي على أي تكرار آخر لـ N من الآحاد المتتالية. على سبيل المثال، عندما N  =  3، تُرمّز الأعداد الصحيحة الموجبة على النحو التالي: 111، 0111، 00111، 10111، 000111، 100111، 010111، 110111، 0000111، 1000111، 0100111، ... في هذه الحالة، يُعطى عدد الترميزات كدالة لطول السلسلة بواسطة متتالية أعداد تريبوناتشي .

بالنسبة للقيود العامة التي تحدد الرموز المسموح بها بعد رمز معين، يمكن الحصول على أقصى معدل للمعلومات من خلال إيجاد احتمالات الانتقال المثلى أولاً باستخدام المشي العشوائي ذي الإنتروبيا القصوى ، ثم استخدام مشفر الإنتروبيا (مع مشفر ومفكك تشفير متبادلين) لترميز رسالة كسلسلة من الرموز التي تحقق احتمالات الانتقال المثلى التي تم العثور عليها.

• أساس النسبة الذهبية
• ترميز نيغافيبوناتشي
• ترقيم أوستروفسكي
• الشفرة العالمية
• فاريكود ، تطبيق عملي
• نظرية زيكندورف
• المشي العشوائي ذو الإنتروبيا القصوى

• ألوش ، جان بول؛ شاليت، جيفري (2003). المتتاليات التلقائية: النظرية، التطبيقات، التعميمات . مطبعة جامعة كامبريدج . ص 105. ISBN  978-0-521-82332-6. Zbl 1086.11015 . 
• فرانكل، أفيزري س.؛ كلاين، شموئيل ت. (1996). "رموز شاملة قوية للإرسال والضغط". الرياضيات التطبيقية المنفصلة . 64 (1): 31-55 . CiteSeerX 10.1.1.37.3064 . doi : 10.1016/0166-218X(93)00116-H . ISSN 0166-218X . Zbl 0874.94026 .   

• ستاخوف، أ.ب. (2009). رياضيات التناغم: من إقليدس إلى الرياضيات المعاصرة وعلوم الحاسوب . سنغافورة: دار النشر العالمية العلمية .