Fibonacci coding

ملف:Fibonacci sequence.svg

تمثيل رسمي لتسلسل فيبوناتشي

في الرياضيات والحوسبة، ترميز فيبوناتشي هو رمز شامل يُشفر الأعداد الصحيحة الموجبة إلى كلمات ترميز ثنائية. إنه مثال على التمثيلات المبنية على أعداد فيبوناتشي. ينتهي كل كلمة ترميز بـ "11" ولا تحتوي على أي حالات أخرى من "11" قبل النهاية.

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

التعريف

لعدد $N\!$، عندما تمثل الأرقام $d(0),d(1),\ldots ,d(k-1),d(k)\!$ أرقام كلمة الترميز التي تمثل العدد $N\!$، نحصل على:

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

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

يمكن إظهار أن هذا الترميز فريد، والحالة الوحيدة لـ "11" في أي كلمة ترميز هي في النهاية (أي خطأ رياضيات (SVG (يمكن تمكين MathML عبر البرنامج المساعد للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(k−1)} و $d(k)$). البت الأخير من اليمين هو أكثر أهمية، والبت الأول من اليسار هو أقل أهمية. بالإضافة إلى ذلك، لا يمكن حذف الأصفار الأولية كما يمكن في الأعداد العشرية.

أول بضعة ترميزات فيبوناتشي موضحة أدناه، بالإضافة إلى ما يُسمى بـ "الاحتمال المفترض"، وهو القيمة التي تحتوي كل رقم على ترميز أصغر حجم في ترميز فيبوناتشي.

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

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

1. ابحث عن أكبر عدد فيبوناتشي يساوي أو يكون أقل من $N$، واطرح هذا العدد من $N$، مع الحفاظ على الباقي.
2. إذا كان العدد المطروح هو العدد فيبوناتشي الذي يحمل الرقم $i$، ضع 1 في الموضع خطأ رياضيات (خطأ في الصياغة): {\displaystyle i−2} في كلمة الترميز (يعتبر الرقم الأيسر هو الموضع 0).
3. كرر الخطوات السابقة، باستبدال الباقي من $N$، حتى يتم الوصول إلى باقي يساوي 0.
4. ضع 1 إضافية بعد الرقم الأيمن في كلمة الترميز.

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

المقارنة مع الرموز الشاملة الأخرى

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

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

المثال

الجدول التالي يظهر أن العدد 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{additional}}\\\hline *&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}$

التعميمات

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

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

انظر أيضاً

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

📰 Article(s) of the same category(ies)

• Golomb coding
• Prediction by partial matching
• Elias omega coding

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Fibonacci coding in English