balanced binary counter algorithm

[notadave]

Of the two provided functions, one counts up, the other down. Both are using the same algorithm, but in inverse direction.
Encode.c takes a normal binary number and returns a balanced number. Decode.c converts the other way.
Unlike any other counter the weight of the binary number never changes. Zero has the same weight as one or any other number.
Even though this is not a normal binary number counter but one that skips possible combinations (that is not how it works / is implemented), the larger, smaller operator for normal binary numbers can be used, as long as it is in the same domain. e.g. a < b equals encode(a) < encode(b).
Due to the implementation with zeros in the unused places, it is a fixed number of ones and zeros counter but I meant it to be the same number of ones and zeros. That is why I call it balanced.
What uses you may have for it I can not know, I use it for channel coding, without the use of tables or other encoded knowledge. The code words are well suited for OOK modulation as used with narrow-band SAW resonators at 315, 433, 866 MHz.
These functions are small as machine code and sufficiently fast for encoding 4b/6b or 6b/8b at 10kBaud. They only require the simplest 8bit RISC instructions that are always (PIC, ATtiny, Z80, 6502) available, the encoder does not even add. Their run time goes up exponentially with the number of bit, so even though the algorithm scales to any number it soon is impractical.
This implementation is done in 'C', it does not need much memory but done in ASM or HDL the implementation would be different, operating on the bit themselves.
The source code is probably best understood by fist looking at encode() and the end of the function to see where and how the result is stored.

More to come

[ledtester]

The book I always first check for combinatorial algorithms is "Combinatorial Algorithms for Computers and Calculators" by Nijenhuis and Wilf published in 1978. Code is presented in pseudo-code and FORTRAN, so it's fairly platform agnostic.

With respect to k-subsets of an n-element set it has algorithms for generating the next (lexicographical) k-subset and also for generating a random k-subset. Indeed, it looks like the encode function has the guts of the next k-subset algorithm in it.

In the academic literature the encode/decode functions are called ranking and unranking -- in case you want to google search for more discussion of these kinds of algorithms. Perhaps the last word on the matter is in section 7.2.1.3 of  Knuth's Art of Computer Programming, "Generating All Combinations". A pre-print was made available in 2005 and is available here as "Pre-fascicle 3A":

http://www.cs.utsa.edu/~wagner/knuth/

[notadave]

In the academic literature the encode/decode functions are called ranking and unranking -- in case you want to google search for more discussion of these kinds of algorithms.

Thanks so much. I did many hours of thinking on this. I knew what I wanted but not what it was called.

[notadave]

With a 2n code word you have (2n over n) balanced combinations. The math is that of the Pascal's triangle . The relevant solutions are the center value in every second row or the diagonal in a table: 1, 2, 6, 20, 70, 252, ... The triangle is the key to shorter run time as the bit positions values can be read from it. For a e.g. 40b/44b code the run time of the presented algorithm would be prohibitive.
Of the (2n)b/(2n+2)b codes only 4b/6b and 6b/8b are truly balanced and optimal. To be balanced and optimal (2n over n)-2 must be greater or equal to 2^n. This is not the case for 8b/10b as 252-2 is smaller than 256. The 2 is to avoid using 00..01..11 and 11..10..00 which would raise the maximum run length by two. Because 8b/10b has a carry, it is actually a 16b/20b code.

4b/6b has the benefit of having two combinations extra I chose 010101 and 101010 to be special purpose because they have a high number of transitions per bit. This way the maximum transitions per bit is 1 and the maximum run-length is 4. RLL(0,4) Compared to a NRZ Signal with a maximum of transitions per bit of 1 and a maximum run-length that is unlimited.
Six bit do not work well with the usual 8 bit, this is why I like 4b/6b the most. Yes, unlike Manchester it needs synchronization and it has 33% redundancy, but that redundancy is worth it as it also provides full single channel bit error detection, limited two channel bit error detection per 4 information bit.
These functions do not provide any error handling, they are part of a chain/stack that ensures synchronization, data flow, framing, final CRC check, error handling, ... none of which is included here. Right in front of the encoding counter you will need a function that skips unwanted combinations. For 4b/6b these are to me: 000111=0d 010101=5d and their inverses 14d and 19d. Other words might be used as special side channel info or for synchronization. That is how I find/mark the start of a frame.
Every channel word is balanced thus after synchronization every single bit error is detected and it is known that one of the four equal channel bit must be wrong. If one of the four unused patterns is found there must have been a two or other even number bit error. As it is known which four information bit are in question it is easy to correct them by adding another 4 bits to what ever correction strength you wish. This will also provide full two-bit-error detection. This is massive error protection and signal shaping at less than twice the bandwidth.

[notadave]

With respect to k-subsets of an n-element set it has algorithms for generating the next (lexicographical) k-subset and also for generating a random k-subset. Indeed, it looks like the encode function has the guts of the next k-subset algorithm in it.

The algorithm to count up can be explained in plain English: To make a step swap a '01' to a '10' and push/sweep/shove all the ones to the right of that swap all the way to the right end.
As usual very simple once you know it, but it took me long to get there.

• 000111
• 001011
• 001101
• 001110
• 010011
• 010101
• 010110
• 011001
• ...

Perhaps the last word on the matter is in section 7.2.1.3 of  Knuth's Art of Computer Programming, "Generating All Combinations".

I started looking at it.

[notadave]

With respect to k-subsets of an n-element set it has algorithms for generating the next (lexicographical) k-subset and also for generating a random k-subset. Indeed, it looks like the encode function has the guts of the next k-subset algorithm in it.

When I started to think about this I did draw a graph (I must not use the T word) and derived the table form of the P-triangle from that. My initial idea was to walk the graph to rank the combinations. That graph is made up of many reoccurring sub-graphs that represent subsets. Every sub-set is generated by the position of a certain digit and the sub-sets in that subset by the "next" digit.
For the small case of n=2+2 the recurrence is not really visible:
{{0011}} {{0101}{0110}} {{1001}{1010}{1100}}
{{   1   }} {{   2   }{   3   }} {{   4   }{   5   }{   6   }}
It begins to show at n=3+3

[notadave]

I now have two variants of a digital circuit for this in VHDL.
They are surprisingly complex because they are less local than a normal counter. There are two carry like signals, one for each digit direction. Unlike for normal counting the carry-over does not cause all lower digits to go from one to zero, that makes it more complex.
I guess I will post them when they are good enough.
This might have another application: radiation hardened circuitry. This creates significant redundancy that can be checked and cause a fail/reset.

[notadave]

Done.
Compared to the C code the VHDL description is very long, not just because there are more and longer names. And it even does less. It does not convert. It can only change it's state in the right sequence.
As mentioned earlier, though this is not a normal binary number counter, the larger, smaller operators (<,>,=) for normal binary numbers can be used, although you might have to flip it around because I used "... to ..." thinking it would not matter.
This VHDL balanced counter with the same number/amount of ones and zeros is fully parametrized and thus may be synthesized for any even number of bit equal or greater to 6. It's size scales linearly.

The basic bit wise element is:

Code: [Select]

LIBRARY ieee;
use ieee.std_logic_1164.all;
ENTITY bit_block IS
GENERIC(
position, ones : positive
);
PORT(
reset_in : IN std_logic;--globales reset
pI_rst_down : IN std_logic;
pI_sta_down : IN std_logic;
pi_state : IN std_logic;
lower_can, pi_moving_up : IN std_logic;
pi_loc_set : IN std_logic;
pi_rst_count : IN std_logic_vector(1 to ones-1);

po_move_higher : OUT std_logic;
po_state_down : OUT std_logic;
po_state_next : OUT std_logic;
po_inhibit : OUT std_logic;
pO_rst_down : OUT std_logic;
pO_rst_count : OUT std_logic_vector(1 to ones-1)
);
end bit_block;

architecture bit_wise of bit_block is

signal preset, ws_mov_hi : std_logic;
signal ws_rst_count : std_logic_vector(1 to ones-1);

begin
preset <= '1' when position <= ones else '0';
po_state_down <=  pi_state;
po_inhibit <= lower_can OR pi_moving_up;
ws_rst_count(1) <= pi_rst_count(1) OR (pi_state AND pI_rst_down);
l_zaehlen : for i in 2 to ones-1 generate
ws_rst_count(i) <= (pI_rst_down AND pi_state AND pi_rst_count(i-1)) OR pi_rst_count(i);
end generate;
pO_rst_count <= ws_rst_count;
ws_mov_hi <= pi_state AND not pI_sta_down AND not lower_can;
po_state_next <= (pi_state AND pI_sta_down AND not reset_in AND not pI_rst_down) OR --kann nicht
                (pi_state AND lower_can AND not reset_in AND not pI_rst_down) OR --braucht nicht
(pi_moving_up AND not reset_in) OR --von links
(pI_rst_down AND pi_loc_set AND not reset_in) OR --alle anderen nach links
                (reset_in AND preset);--reset
po_move_higher <= ws_mov_hi;
pO_rst_down <= (ws_mov_hi OR pI_rst_down) AND not reset_in;
end bit_wise;
And this block then chains them together:

Code: [Select]

LIBRARY ieee;
use ieee.std_logic_1164.all;

ENTITY balancedcounter IS
  GENERIC(
ones : positive := 3
);
  PORT(
  clk, enable, reset : IN std_logic;
  po_count : OUT std_logic_vector(1 to 2*ones)
  );
END balancedcounter;

ARCHITECTURE bitblock OF balancedcounter IS

--constant ones : positive := 3;

COMPONENT bit_block IS
GENERIC(
position, ones : positive
);
PORT(
reset_in : IN std_logic;--globales reset
pI_rst_down : IN std_logic;
pI_sta_down : IN std_logic;
pi_state : IN std_logic;
lower_can, pi_moving_up : IN std_logic;
pi_loc_set : IN std_logic;
pi_rst_count : IN std_logic_vector(1 to ones-1);

po_move_higher : OUT std_logic;
po_state_down : OUT std_logic;
po_state_next : OUT std_logic;
po_inhibit : OUT std_logic;
pO_rst_down : OUT std_logic;
pO_rst_count : OUT std_logic_vector(1 to ones-1)
);
end component bit_block;

type sindmat is array (0 to 2*ones-1) of std_logic_vector(1 to ones-1);

--Signale:
signal ws_sta_next : std_logic_vector(1 to 2*ones);-- logik zu Register
signal ws_sta_now : std_logic_vector(1 to 2*ones);-- Register zu Logik
signal verbinder_zustand_innen_links : std_logic_vector(1 to 2*ones-1);
signal verbinder_ruecken : std_logic_vector(1 to 2*ones-1);
signal verbinder_reset_links : std_logic_vector(1 to 2*ones-1);--selektives inneres reset nach links
signal verbinder_links_meldet_potential : std_logic_vector(1 to 2*ones-1);
signal verbind_sind : sindmat;--propagiert die zu resetenen Einsen
signal local_sind_vec : std_logic_vector(1 to ones-1);
signal local_sind : std_logic_vector(1 to 2* ones);

BEGIN

l_register : process(clk)
begin
if clk'EVENT and clk = '1' then
if enable = '1' then
ws_sta_now <= ws_sta_next;
end if;
end if;
end process;

local_sind_vec <= verbind_sind(0);
l_locsind : for i in 1 to 2* ones generate
local_sind(i) <= local_sind_vec(i) when i < ones else '0';
end generate;

l_gen : for i in 2 to 2*ones-1 generate
l_component_lable : bit_block
GENERIC MAP(
position => i,
ones => ones
)
PORT MAP(
reset_in => reset,
pI_rst_down => verbinder_reset_links(i),
pI_sta_down => verbinder_zustand_innen_links(i),
pi_state => ws_sta_now(i),
lower_can => verbinder_links_meldet_potential(i-1),
pi_moving_up => verbinder_ruecken(i-1),
pi_loc_set => local_sind(i),
pi_rst_count => verbind_sind(i),
--outs:
po_move_higher => verbinder_ruecken(i),
po_state_down => verbinder_zustand_innen_links(i-1),
po_state_next => ws_sta_next(i),
po_inhibit => verbinder_links_meldet_potential(i),
pO_rst_down => verbinder_reset_links(i-1),
pO_rst_count => verbind_sind(i-1)
);
end generate;

l_ganzrechts : bit_block
GENERIC MAP(
position => 2*ones,
ones => ones
)
PORT MAP(
reset_in => reset,
pI_rst_down => '0',
pI_sta_down => '1',
pi_state => ws_sta_now(2*ones),
lower_can => verbinder_links_meldet_potential(2*ones-1),
pi_moving_up => verbinder_ruecken(2*ones-1),
pi_loc_set => local_sind(2*ones),
pi_rst_count => (others => '0'),

po_move_higher => open,
po_state_down => verbinder_zustand_innen_links(2*ones-1),
po_state_next => ws_sta_next(2*ones),
po_inhibit => open,
pO_rst_down => verbinder_reset_links(2*ones-1),
pO_rst_count => verbind_sind(2*ones-1)
);

l_ganzlinks : bit_block
GENERIC MAP(
position => 1,
ones => ones
)
PORT MAP(
reset_in => reset,
pI_rst_down => verbinder_reset_links(1),
pI_sta_down => verbinder_zustand_innen_links(1),
pi_state => ws_sta_now(1),
lower_can => '0',
pi_moving_up => '0',
pi_loc_set => local_sind(1),
pi_rst_count => verbind_sind(1),

po_move_higher => verbinder_ruecken(1),
po_state_down => open,
po_state_next => ws_sta_next(1),
po_inhibit => verbinder_links_meldet_potential(1),
pO_rst_down => open,
pO_rst_count => verbind_sind(0)
);

po_count <= ws_sta_now;

END ARCHITECTURE bitblock;


[chickenHeadKnob]

The book I always first check for combinatorial algorithms is "Combinatorial Algorithms for Computers and Calculators" by Nijenhuis and Wilf published in 1978. Code is presented in pseudo-code and FORTRAN, so it's fairly platform agnostic.

With respect to k-subsets of an n-element set it has algorithms for generating the next (lexicographical) k-subset and also for generating a random k-subset. Indeed, it looks like the encode function has the guts of the next k-subset algorithm in it.

In the academic literature the encode/decode functions are called ranking and unranking -- in case you want to google search for more discussion of these kinds of algorithms. Perhaps the last word on the matter is in section 7.2.1.3 of  Knuth's Art of Computer Programming, "Generating All Combinations". A pre-print was made available in 2005 and is available here as "Pre-fascicle 3A":

http://www.cs.utsa.edu/~wagner/knuth/

In the mathematical/Combinatorics literature these structured sets are called block designs, with a sub-type called balanced incomplete block designs (BIBD's) having many papers. At least I think that is what notadave is playing with.
wiki: https://en.wikipedia.org/wiki/Block_design

[notadave]

I find it hard to search/find anything on this topic due to too many non related results, but I now found this:
https://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/
Same thing, different method.