Parity-Step Code

Parity-Step Code is a Universal Coding of Integers (UCI) inspired by Collatz conjecture.

Encoding positive integer n is dead simple:

function* encodeParityStep(n) {
  while (n !== 1) {
    if (n % 2 === 0) {
      n = n / 2
      yield 0
    } else {
      n = n - 1 // differs from Collatz function `n = 3 * n + 1`
      yield 1
    }
  }
  yield 1
  yield 1
}

• Each codeword ends with 11. As with Fibonacci code, 11 does not appear anywhere else in the codeword.
• The codeword length is not monotonically increasing. It is shorter for $2^{n}$ and longer for $2^{n}-1$.

| n | Parity-Step Code | Fibonacci Code (npm) | Exponential-Golomb Code (k=0) (npm) | Varint (npm) | | ---------:| ----------------------------:| ------------------------------:| ---------------------------------------:| ------------------------:| | 0 | - | - | 1 | 00000000 | | 1 | 11 | 11 | 010 | 00000001 | | 2 | 011 | 011 | 011 | 00000010 | | 3 | 1011 | 0011 | 00100 | 00000011 | | 4 | 0011 | 1011 | 00101 | 00000100 | | 5 | 10011 | 00011 | 00110 | 00000101 | | 6 | 01011 | 10011 | 00111 | 00000110 | | 7 | 101011 | 01011 | 0001000 | 00000111 | | 8 | 00011 | 000011 | 0001001 | 00001000 | | 9 | 100011 | 100011 | 0001010 | 00001001 | | 10 | 010011 | 010011 | 0001011 | 00001010 | | 11 | 1010011 | 001011 | 0001100 | 00001011 | | 12 | 001011 | 101011 | 0001101 | 00001100 | | 13 | 1001011 | 0000011 | 0001110 | 00001101 | | 14 | 0101011 | 1000011 | 0001111 | 00001110 | | 15 | 10101011 | 0100011 | 000010000 | 00001111 | | 16 | 000011 | 0010011 | 000010001 | 00010000 | | 100 | 0010001011 | 00101000011 | 0000001100101 | 01100100 | | 1,000 | 0001001010101011 | 0000010000000011 | 0000000001111101001 | 1110100000000111 | | 1,023 | 10101010101010101011 | 0100000100000011 | 000000000010000000000 | 1111111100000111 | | 1,024 | 000000000011 | 0010000100000011 | 000000000010000000001 | 1000000000001000 | | 10,000 | 0000100001010100011 | 01010001000001001011 | 000000000000010011100010001 | 1001000001001110 | | 16,383 | 1010101010101010101010101011 | 010000010001001001011 | 00000000000000100000000000000 | 1111111101111111 | | 16,384 | 0000000000000011 | 001000010001001001011 | 00000000000000100000000000001 | 100000001000000000000001 | | 100,000 | 00000100100101000001011 | 1010101001001000001010011 | 000000000000000011000011010100001 | 101000001000110100000110 | | 1,000,000 | 000000100010000010010101011 | 000000001010000000000010100011 | 000000000000000000011110100001001000001 | 110000001000010000111101 |

Usage

$ npm i @luncheon/parity-step-code

API

import { encodeParityStep, decodeParityStep } from "@luncheon/parity-step-code";

encodeParityStep(3)
// => Generator<0 | 1>

encodeParityStep(3).toArray()
// => [1, 0, 1, 1]

encodeParityStep(3).reduce((x, y) => x + y, "")
// => "1011"
// can't wait https://github.com/tc39/proposal-iterator-join

decodeParityStep([1, 0, 1, 1])
// => 3

decodeParityStep(encodeParityStep(3))
// => 3

CLI

$ npx @luncheon/parity-step-code 3 4 5 10-20 0x80
   3 1011
   4 0011
   5 10011
  10 010011
  11 1010011
  12 001011
  13 1001011
  14 0101011
  15 10101011
  16 000011
  17 1000011
  18 0100011
  19 10100011
  20 0010011
 128 000000011

License

WTFPL