Can it represent both signs?

Yes. The alternating place values encode positive and negative integers without requiring a separate sign bit in this convention.

Why does 11 identify the end?

Canonical coefficient payloads contain no adjacent ones; appending one after the final selected coefficient creates the first such pair.

Is zero automatically covered?

Not by the nonzero codeword convention described here. A format that needs zero must specify an extension or mapping.

AI Glossary / MLOps and deployment / Advanced

Negafibonacci coding

Definition

Negafibonacci coding represents nonzero signed integers using Fibonacci numbers with negative indices, then turns that representation into a self-delimiting binary codeword. Alternating positive and negative place values allow the sign to be carried by the representation itself. A final marker identifies where each encoded integer ends in a stream.

What it means

Ordinary binary uses positive place values such as 1, 2, 4, and 8. Negafibonacci representation instead uses the sequence F−1=1, F−2=−1, F−3=2, F−4=−3, F−5=5, F−6=−8, and so on.

An integer is expressed as a sum of selected place values, with each coefficient either zero or one and no adjacent coefficients both one. For example, four can be represented as five minus one, using positions five and two.

The mathematical representation and the transmitted codeword are related but not identical. A representation may be printed with the largest-index position first. The coding convention described here sends coefficients from F−1 upward and appends an extra one after the final nonzero coefficient.

How it works

First obtain the unique nonconsecutive negative-index Fibonacci representation of the integer. Bunder's paper establishes the representation and gives a construction algorithm. Because signs alternate, an encoder should use a correct negafibonacci procedure rather than blindly applying the usual positive-number Fibonacci greedy rule.

Write the selected coefficients in increasing absolute index order, stopping at the highest selected position. The last coefficient is one. Append another one, creating a terminal pair 11. No such pair occurs inside the coefficient payload because adjacent selected positions are forbidden.

A decoder scans from the start of a codeword until the first 11. It removes the final marker one, interprets the remaining coefficients against the agreed place values, and adds the selected values. It then restarts the place-value index for the next codeword. The basic nonzero-integer format needs an additional agreed convention if zero must be represented.

Three practical examples

1. A compression exercise encodes positive and negative prediction residuals without a separate sign field. It compares actual code lengths with another signed-integer mapping instead of assuming one approach must always be smaller.

2. A streaming-format prototype uses terminal markers to identify successive integer boundaries without storing a separate length for each integer. The surrounding format still specifies how the stream starts and ends and how invalid input is handled.

3. A software verification lesson tests representation uniqueness and round-trip decoding across a range of integers. Small positive and negative examples expose mistakes in coefficient order, marker removal, and sign handling.

Think of it this way

Think of paying a balance with tokens that alternately add and subtract value. The selected tokens determine both the magnitude and the sign, so no separate “negative” flag is necessary.

The analogy is limited: these are mathematical place values, not freely interchangeable coins. The nonadjacency rule is essential to the canonical representation, and the terminal marker is a separate coding device that has no monetary counterpart.

Worked example

Encode the integer four. With place values ordered (1,−1,2,−3,5), select −1 and 5. The coefficient sequence in transmission order is 01001, whose weighted sum is 0×1+1×(−1)+0×2+0×(−3)+1×5=4.

Append the marker one to obtain 010011. The first adjacent pair 11 is at the end. The decoder removes only the final marker bit, leaving the original five coefficients.

For minus four, use −1−3. The transmission-order coefficients are 0101, and appending one produces 01011. Joining the two codewords gives 01001101011. Starting at the left, the decoder identifies 010011, resets its place-value count, and then identifies 01011, recovering (4,−4).

The two codewords use six and five bits respectively. This small comparison illustrates that opposite signs of equal magnitude need not have equal code lengths. It does not establish that the format compresses a realistic dataset better than fixed-width integers or other variable-length codes.

Illustrative case study

Fictional case: ResidualForge tests a compact format for signed differences in a laboratory data stream. A developer initially reverses each printed representation twice, causing valid-looking codewords to decode to the wrong values.

The team adds hand-calculated vectors for both signs and a test that concatenates several codewords without separators. It also defines how zero residuals are mapped, because the nonzero coding rule alone does not provide that requirement.

Before choosing a format, the team compares total storage including headers and implementation complexity. This hypothetical case illustrates specification and verification, not an assertion that negafibonacci coding is common in commercial telemetry or that it delivered a measured saving.

Common misconceptions and mistakes

“Negative Fibonacci numbers” means Fibonacci numbers extended to negative indices, not a sequence containing only negative values. The signs alternate.

The final marker bit is not another selected Fibonacci place. Including it in the weighted sum changes the decoded integer. Likewise, the direction in which digits are printed must not be confused with their transmission order.

Self-delimiting does not mean error-correcting. A corrupted bit can change a value or a boundary. A storage or transmission system may still need checksums, length limits, and recovery rules. The code is also not encryption: anyone knowing the convention can decode it.

Business use

The business relevance is mainly as a specialized integer-coding option and an instructive example of self-delimiting representation. Its suitability depends on the distribution of values, decoding cost, and interoperability requirements.

Measure complete encoded size on representative data, including zero handling and framing overhead. Compare against simpler alternatives and document the exact bit convention. A mathematically elegant representation is useful only when it meets the practical storage, performance, and maintenance needs of the system using it.

Check your understanding

In codeword 010011, why is the last one excluded from the weighted sum?

Answer: It is the termination marker. The payload is 01001, selecting −1 and 5 and therefore representing four.

Related terms

Fibonacci coding
Prefix code
Lossless compression
universal integer code
variable-length coding
signed integer
stream framing

Learn next

Encode and decode several small integers of both signs, explicitly separating printed representation, transmission-order coefficients, and marker. Then compare bit counts on a synthetic residual distribution with a clearly specified zero convention.

Sources

Primary mathematical reference: M. W. Bunder, Zeckendorf Representations Using Negative Fibonacci Numbers, https://www.fq.math.ca/Scanned/30-2/bunder.pdf . Representation records: https://oeis.org/A215022 and https://oeis.org/A215023 . These establish the underlying representations; the stated stream convention, decoding explanation, and numerical exercises are explicitly developed here.

Previous: Necessary condition analysis Next: Negation