کدگذاری نگافیبوناچی

در ریاضیات، کدگذاری نگافیبوناچی (انگلیسی: Negafibonacci coding) یک کد جامع (فشرده‌سازی داده‌ها) است که اعداد صحیح غیرصفر را به کلمات کد دودویی تبدیل می‌کند. این روش شبیه به کدگذاری فیبوناچی است، با این تفاوت که امکان نمایش هر دو دستهٔ اعداد صحیح مثبت و منفی را فراهم می‌سازد. همۀ کدها با «۱۱» پایان می‌یابند و پیش از انتها هیچ «۱۱» دیگری در آن‌ها وجود ندارد.

روش کدگذاری

گام‌های زیر نحوۀ کدگذاری یک عدد صحیح غیرصفر $x$ را شرح می‌دهند. توجه داشته باشید که $f$ نشان‌دهندۀ دنبالۀ نگافیبوناچی است.

1. اگر $x$ مثبت باشد، بزرگ‌ترین عدد صحیح فرد منفی مانند $n$ را محاسبه کنید به‌گونه‌ای که مجموع جملات فرد منفی دنبالۀ نگافیبوناچی از ۱- تا $n$ با گام ۲-، بزرگ‌تر یا مساوی با $x$ شود:
   $n\in \{-\left(2k+1\right),k\in [0,\infty [\},\quad \sum _{i=-1,\;i\;{\text{فرد}}}^{n-2}f(i)<x\leq \sum _{i=-1,\;i\;{\text{فرد}}}^{n}f(i).$
   اگر $x$ منفی باشد، بزرگ‌ترین عدد صحیح زوج منفی مانند $n$ را محاسبه کنید به‌گونه‌ای که مجموع جملات زوج منفی دنبالۀ نگافیبوناچی از ۰ تا $n$ با گام ۲-، کوچک‌تر یا مساوی با $x$ شود:
   $n\in \{-2k,k\in [2,\infty [\},\quad \sum _{i=-2,\;i\;{\text{زوج}}}^{n-2}f(i)>x\geq \sum _{i=-2,\;i\;{\text{زوج}}}^{n}f(i)$
2. یک رقم ۱ در بیت $|n|$ـُم کلمۀ دودویی قرار دهید. سپس مقدار $f(n)$ را از $x$ کم کنید.
3. فرایند را از گام ۱ با مقدار جدید x تکرار کنید تا زمانی که مقدار آن به ۰ برسد.
4. برای پایان کدگذاری، یک رقم ۱ در سمت چپ کلمۀ دودویی به‌دست‌آمده بیفزایید.

برای رمزگشایی یک کلمۀ دودویی کدگذاری‌شده، چپ‌ترین رقم ۱ را از کلمۀ دودویی حذف کنید؛ زیرا این رقم تنها برای نشان دادن پایان عددِ کدگذاری‌شده به کار رفته است. سپس به بیت‌های باقی‌مانده، مقادیر دنبالۀ نگافیبوناچی را از ۱- (۱، ۱-، ۲، ۳-، ۵، ۸-، ۱۳...) اختصاص دهید و تمام مقادیری را که متناظر با بیت ۱ هستند با یکدیگر جمع کنید.

نمایش نگافیبوناچی

الگو:دستگاه‌های عددنویسی

کدگذاری نگافیبوناچی ارتباط نزدیکی با نمایش نگافیبوناچی دارد؛ نوعی دستگاه عددنویسی ارزشی که گاهی ریاضیدانان آن را به کار می‌برند. کد نگافیبوناچی برای یک عدد صحیح غیرصفر معین، دقیقاً همان نمایش نگافیبوناچی آن عدد است، با این تفاوت که ترتیب ارقام آن معکوس شده و یک رقم «۱» اضافی نیز به انتهای آن افزوده می‌شود. کد نگافیبوناچی برای همۀ اعداد منفی دارای تعداد ارقام فرد است، در حالی که کد مربوط به همۀ اعداد مثبت تعداد ارقام زوج دارد.

جدول

کد مربوط به اعداد صحیح از ۱۱- تا ۱۱ در جدول زیر آمده است.

عدد	نمایش نگافیبوناچی	کد نگافیبوناچی
۱۱-	۱۰۱۰۰۰	۰۰۰۱۰۱۱
۱۰-	۱۰۱۰۰۱	۱۰۰۱۰۱۱
۹-	۱۰۰۰۱۰	۰۱۰۰۰۱۱
۸-	۱۰۰۰۰۰	۰۰۰۰۰۱۱
۷-	۱۰۰۰۰۱	۱۰۰۰۰۱۱
۶-	۱۰۰۱۰۰	۰۰۱۰۰۱۱
۵-	۱۰۰۱۰۱	۱۰۱۰۰۱۱
۴-	۱۰۱۰	۰۱۰۱۱
۳-	۱۰۰۰	۰۰۰۱۱
۲-	۱۰۰۱	۱۰۰۱۱
۱-	۱۰	۰۱۱
۰	۰	(قابل کدگذاری نیست)
۱	۱	۱۱
۲	۱۰۰	۰۰۱۱
۳	۱۰۱	۱۰۱۱
۴	۱۰۰۱۰	۰۱۰۰۱۱
۵	۱۰۰۰۰	۰۰۰۰۱۱
۶	۱۰۰۰۱	۱۰۰۰۱۱
۷	۱۰۱۰۰	۰۰۱۰۱۱
۸	۱۰۱۰۱	۱۰۱۰۱۱
۹	۱۰۰۱۰۱۰	۰۱۰۱۰۰۱۱
۱۰	۱۰۰۱۰۰۰	۰۰۰۱۰۰۱۱
۱۱	۱۰۰۱۰۰۱	۱۰۰۱۰۰۱۱

جستارهای وابسته

• اعداد فیبوناچی
• پایه نسبت طلایی
• قضیه زکندورف

منابع

آثار ذکرشده

الگو:آغاز جعبه پیوندها

• Knuth, Donald (2008). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting of the Mathematical Association of America. San Jose, California.
• Knuth, Donald (2009). هنر برنامه‌نویسی رایانه. Vol. 4, Fascicle 1: Bitwise Tricks & Techniques, Binary Decision Diagrams. Addison-Wesley. ISBN 978-0-321-58050-4. In the pre-publication draft of section 7.1.3 see in particular pp. 36–39.
• Margenstern, Maurice (2008). Cellular Automata in Hyperbolic Spaces. Advances in unconventional computing and cellular automata. Vol. 2. Archives contemporaines. p. 79. ISBN 9782914610834.

الگو:پایان جعبه پیوندها

جستارهای وابسته

• اعداد فیبوناچی

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Negafibonacci coding». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۸ اوت ۲۰۲۶.