Comma code

A comma code is a type of prefix-free code in which a comma, a particular symbol or sequence of symbols, occurs at the end of a code word and never occurs otherwise. This is an intuitive way to express arrays.

For example, Fibonacci coding is a comma code in which the comma is 11. 11 and 1011 are valid Fibonacci code words, but 101, 0111, and 11011 are not.

Examples

• Unary coding, in which the comma is 0. This allows NULL values (when the code and comma is a single 0, the value can be taken as a NULL or a 0).
• Fibonacci coding, in which the comma is 11. The comma of 11 implies that the two codes that are being used to depict data are 0,10. Which can translate to the exact bits 0,1 when representing arbitrary bit strings or numbers. If representing arbitrary bit strings or numbers using this method, one would simply write a '0' for a 0 and a '10' for a 1, and a '11' for the comma / separator and repeat the separator/comma for a NULL. That constructs a Fibonacci lookalike code which looks like a Fibonacci code but translates directly to the bit string rather than the number represented by the Fibonacci series. With standard Fibonacci coding, one is representing every integer as a Fibonnaci code, and the mapping of integer->code->integer encoding and decoding require Fibonacci analysis. With the Fibonacci lookalike codes, one takes the bitstring or a bitwise number and writes it as a series of 0s and 10s and ends the string/number with a '11'. This allows one to express arrays.

The Fibonacci code can be deconstructed into the data part and the pre-comma ( not the 11 but the count of 1s in the data ). This is a punctured Elias code, which simply writes the count of 1s in the digits to follow. Or one can construct the Fibonacci code from the punctured Elias code by writing a 10 for every 1 in the data and a 11 for the last 1 in the data string. If the data is a random bitstring, then one can simply write 0 for 0 in the bitstring and 10 for 1 in the bitstring and a 11 as the comma/separator. This allows a NULL value which is simply 11.

This method allows a bitstring or number of length n to be expressed in 1.5n+2 bits assuming 0s and 1s are present in equal measure in the data.

• Loaded comma in Fibonacci lookalike codes - If there is guaranteed to be one bit in the bitstring, then that can be placed verbatim after the comma '11' and the rest of the bits translated 0 -> 0 and 1 -> 10.

This method allows a non null bitstring to be expressed in 1.5n+1.5 bits assuming 0s and 1s are present in equal measure in the data.

• All Huffman codes can be converted to comma codes by prepending a 1 to the entire code and using a single 0 as a code and the comma.

The definition of word being a number of symbols ending in a comma, the equivalent of a space character.

• 50% commas in all data axiom – All implied data specifically variable length bijective data can be shown to be consisting of exactly 50% of commas.

All scrambled data or suitably curated same-length data exhibits so called implied probability ( if it is a valid code then the probability of its occurrence is ${\displaystyle {\frac {1}{2^{length}}}}$).

Such data that can be termed 'generic data' can be analysed using any interleaving unary code as headers where additional bijective bits (equal to the length of the unary code just read) are read as data while the unary code serves as an introduction or header for the data. This header serves as a comma. The data can be read in an interleaving fashion between each bit of the header or in post read fashion when the data is only read after the entire unary header code is read like Chen-Ho encoding.

It can be seen by random walk techniques and by statistical summation that all generic data has a header or comma of an average of 2 bits and data of an additional 2 bits (minimum 1).

This also allows for an inexpensive base increase algorithm before transmission in non binary communication channels, like base-3 or base-5 communication channels.

Where '?' is '1' or '2' for the value of the bijective digit that requires no further processing.

Of course we use a single comma to separate each field of data, therefore showing that all the data consists of 50% of commas. The cost-per-character quotient of higher base communication has to maintain near logarithmic values ${\textstyle {\frac {log(base)}{log(2)}}}$for the data and less than 2-bits for the comma character to maintain cost effectiveness here.

This method has an assurance of a '1' or '2' after every comma and this property can be useful when designing around timing concerns in transmission.

It can be somewhat expensive to convert a known binary value ( last value underlined does not technically require conversion to ternary ) to ternary ( we are considering the comma as digit '3' ), unless ternary bit costs are reduced to similar to binary bit costs, so this bit can be multiplexed in a separate binary channel if costs agree (this may require a read of an additional 'tail'/trailing portion of 2-bits of useful data or an entire unary code known to be around 2 bits as padding for the binary channel (from after the first bit of the first change as this is not an instantly-decodable code, simply read if using an instantly decodable unary code) to be around ${\displaystyle 3}$ bits similar to the 2 average ternary bits remaining on the primary channel equivalent to ${\textstyle 2*{\frac {log(3)}{log(2)}}=3.17}$ bits before cost comparisons are factored in). The padding is to try and ensure that relevant data across streams arrive at similar times to each other as otherwise we would have one bit ( the underlined last bit above ) in the binary channel and around 3.17 bits in the ternary channel ( including just comma for all the commas ) ( again not factoring in a completely different mode of transmission with possibly different latency ).

Not considering multiplexing, this method has a read efficiency of 3 ternary digits for a read of 4 binary bits or 1.33 bits. Or ${\textstyle {\frac {4/3}{\frac {log(3)}{log(2)}}}=84.12\%}$

This method allows a bitstring or number of length n to be expressed in 2n bits assuming 0s and 1s are present in equal measure in the data.

• 66.66% (2/3) commas in all data axiom - All implied data specifically variable length data can be shown to be consisting of exactly 66.66% (2/3) of commas.

Where '?' is '1' or '2' for the value of the bijective digit that requires no further processing. This method results in statistical similarity to a simple 'implied read' of Huffman base 3 codes: 0,10,11 (net 2/3 or 66.66% commas).

It can be seen by random walk techniques and by statistical summation that all generic data has a header or comma of an average of 2 bits and data of an additional 1 bit (minimum 0).

This has no assurance of a '1' or '2' after every '0' (comma) a property that can be useful when designing around timing concerns in transmission.

This method has a read efficiency of 2 ternary digits for a read of 3 binary bits or 1.5 binary bits/ternary digit. Or ${\textstyle {\frac {3/2}{\frac {log(3)}{log(2)}}}=94.64\%}$

This method allows a bitstring or number of length n to be expressed in 2n+1 bits assuming 0s and 1s are present in equal measure in the data. One can assume that the value 0 is 0 bits or an empty string "" followed by the 1.

• 34.375% | 31.25% (~ 1/3) write commas for efficiency gains using number partitioning – Implied reads and writes using number partitioning techniques ('m' numbers divided into 'n' partitions result in n^m permutations) similar to Chen-Ho and Hertz encoding show greater efficiency of both reads and writes similar to nearly random distribution. Thus the use of codes makes less sense and the use of higher bases becomes more important. Similarly, a 'write' comma becomes any number in the base, a 'read' comma is the header shown below, Huffman base 4 codes: 0,10,110,111.

The main advantage to this technique apart from higher efficiency is that there is no base conversion required which would require the entire stream to be read first and then converted. The disadvantage is that the average number length becomes higher and similar to random number generation and timing concerns that govern ternary transmission come to the fore. With m=2 and n=2, we get, not forgetting that a value of '(2)' is essentially 0-bits:

This method therefore has a read efficiency of 2 ternary digits for a read of ${\textstyle 50*3+25*3+12.5*4+12.5*3=3.125}$ binary bits or 1.5625 binary bits/ternary digit. Or ${\textstyle {\frac {3.125*{\frac {1}{2}}}{\frac {log(3)}{log(2)}}}=98.58\%}$.

A write efficiency of 2 ternary digits for a write of ${\textstyle {\frac {4}{9}}*3+{\frac {2}{9}}*3+{\frac {2}{9}}*4+{\frac {1}{9}}*3=3.22}$ bits or 1.61 binary bits/ternary digit, or ${\textstyle {\frac {\frac {log(3)}{log(2)}}{{\frac {29}{9}}*{\frac {1}{2}}}}=98.38\%}$

• Cardinal numbers for efficient base conversion – Since it has been ascertained that comma codes are very similar to base conversion, the only concern being efficiency and timing, the direct conversion/mapping of 19 binary bits ${\textstyle 2^{19}=524288}$ numbers to 12 ternary trits ${\textstyle 3^{12}=531441}$ numbers allow for an efficiency of ${\textstyle {\frac {2^{19}}{3^{12}}}=98.65\%}$ or ${\textstyle {\frac {log_{3}{2^{19}}}{12}}=99.9\%}$ efficiency depending upon the method of calculation. This works because ${\textstyle 2^{19}<3^{12}}$ and ${\textstyle 2^{19}}$≃ ${\textstyle 3^{12}}$. This of course is more of a theoretical construct and has no mention about timing when trying to apply this to ternary transmission methods. It does however leave ${\textstyle 531441-524288=7153}$ codes to design around timing concerns.

See also

• Self-synchronizing code

References