Questions regarding Wrapper's state machine (bug?)

[danilo-bc]

A few questions appeared when analysing the current wrapper module (specifically MReSC, but possibly applicable for all types).

1 - I recognize it uses the count register to count from all 0 to all 1 and check the done status basically when it overflows. This means it has 256 states: 0x00 up to 0xFF. This way, if the true answer to the stochastic function is 1, z_bin will try to add 1 256 times, which will result in an overflow and z_bin = 0 in the end.

Either this assumption is right and the SC works because it's improbably all bits will sum correctly, or it is wrong (maybe it adds 255 times and I'm overlooking it), but that would make z_bin = 255/256, which is also not how stochastic computing is supposed to work.

This concern is linked to the fact that the user can choose WBG as generators and, theoretically, they would produce exact SN representations, which linked to proper correlation considerations, would give a precise answer, that could be 1!

2 - Is the restart signal in LFSR modules necessary? As long as Reset pushes LFSRs to their seed values, they'll have their designed purposes. This leads to the main question: is restarting LFSRs for each calculation necessary? They're already pretty stabilished pseudo-random sources, as long as they've been set with their seeds, they'll have their periodic behaviour, with or without 'restarting' them, and that wouldn't affect SC performance.

[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.