Questions regarding Wrapper's state machine (bug?) about scsynth

[arminalaghi]

Thanks for the comments!

About #1: Great catch! This is a bug in the wrapper. Usually, we assume a stochastic number (SN) of length N=2^m can be represented by an m-bit binary number. But as you noticed, this is wrong. A bit-stream of length N, represents N+1 possible values (vs. N numbers represented by an m-bit binary number). On the input side (when generating SNs out of binary inputs), there is no problem because we leave out one code (usually the all-1 code). In other words, most SNGs never generate a SN number of value 1. They usually go up to (2^m-1)/2^m. Using the same logic, we assumed that the all-1 SN does not appear at the output. This is obviously a wrong assumption, and the counter will overflow in this case. The solution would be to add one more bit z_bin.

About #2: Your observation is correct. In a normal operation, the LFSR will return to its original state and there is no need to reset. Also, if a reset is needed, the asynchronous reset signal can be used. However, it is customary to have a synchronous reset signal for the circuit as well. Imagine the SC circuit being controlled by some FSM or CPU, and imagine a scenario in which FSM decide to stop the operation mid-way, and perhaps start a new operation (this can happen if the FSM is monitoring the output and using progressive precision to make a decision). In this case, the FSM wants to bring the LFSRs back to their original seed, and the synchronous "restart" signal is the more graceful way of doing in, instead of the asynchronous "reset" which is usually used at start up time.

[danilo-bc]

Alright, thanks for the feedback as well!

I thought a simple compatibility solution for Conv->Stoch->Conv would simply use a 2^m-1 bit stream, instead of 2^m. This way, we'd have all 0 through all 1, summing up to 255. Then, we'd only have to think each bit in the stream equals to 1/2^m as usual. This keeps all the precision remarks made, but gives up being able to output "1", making the range [0,1] into [0,1).

I believe this is not such a straightforward step to make, since it questions Stochastic Computing's theory head on, but it seems to make sense. If, say, a 3-bit binary number represents numbers from 0 to 7, 8 codes, a 7-bit stochastic stream is necessary to represent it equally, meaning the sum of bits 1 will range from 0 to 7 as well. This requires a bit of analysis on the input SNG.

Considering the simplest SNG circuit, the comparator, we're comparing if the input value is higher than a certain random number with same number of bits. This means that 0 can correctly be represented as 0, because 0>randn always yields 0. When we compare on the higher end, though, 7>randn is only true for rand != 7. This means that 7 is already being represented in a wrong way. If the condition is fixed by making the condition >= instead of >, then the 0 case will break.

This still doesn't take into consideration that sequences all-1 and all-0 may not be suitable for operations, because they, themselves, may cause correlation issues.

The partial conclusions, then, are:
1 - 2^m-1 stochastic streams may be adopted, but it requires altering either the natural state-machine to stop before overflow or add a new bit for z_bin, which doesn't 'feel right' since the all-1 state rarely, if ever, occurs.
2 - The comparator is not the best way to convert from conventional to binary because it's already unable to represent a value
3 - Maybe the optimal way is not to map the numbers of interest in [0,1] (example: [0,255] into [0,1]), but maybe [0,255] into [0.2,0.8]. This forces the exclusion of 'bad' values and may be able to increase accuracy in systems.

Regarding the LFSR reset/restart in the state machine, I feel like it needs to be reviewed for different length LFSRs (you can't simply restart an 11-bit LFSR at the same time as an 8-bit LFSR), but this issue doesn't require immediate attention, since the feature of having different LFSR lengths doesn't currently apply to the project. This way, it's possible to focus on the actual bugs instead of introducing new (maybe buggy) features.

[arminalaghi]

Forgot to respond to this.
To have stochastic bit-streams of length 2^m-1 with the current setup, we need to exclude the all-zero state of the LFSR (which is artificially added, BTW).

Representing numbers inside smaller intervals (e.g., [0.2 0.8]) has been used in the literature. I can't find the paper right now, but Wekang Qian is among the authors.