

Stochastic Computation applied to the design of Error Correcting Decodersby Gord Harling, Dr. Shie Mannor, Dr. Warren Gross (WideSail) ABSTRACT We describe the application of stochastic computation to a family of errorcorrecting decoders. We have applied this technology to the Low Density Parity Check (LDPC) codes first described by Gallagher in the 1960s. LDPC is the highest performance error correcting code known to date and is used in IEEE standards including WiFi, WiMAX, DVBS2, and 10 GbE. Although the coding technique has only recently been rediscovered as semiconductor technology made it economically viable most implementations are expensive in circuit area and power consumption. Although architectures have been devised to reduce the cost they suffer from performance loss due to the shortcuts taken to reduce circuit size. We have completed the design and layout of a LDPC block decoder with greatly reduced size and power consumption. The use of stochastic computation reduces the effects of quantization error which is a limiting factor in the performance of error correcting decoders based on conventional bitserial or partially parallel architectures. We will present results demonstrating the performance of our stochastic “bitstream” technology. Introduction Generating stochastic streams in theory requires a source of randomness. Our studies have indicated that truly random numbers are not necessary and that pseudorandom (repeatable, “randomlooking”) sequences are enough. Moreover, our results show that even pregenerating a small number of pseudorandom numbers and then storing them in memory in the decoder does not degrade performance. Therefore, in practice, stochastic decoders do not require extremely high entropy and can be predictable and controllable. We perform bittrue simulations to model the exact operation of the hardware. An essential component of a stochastic design is the comparator shown in Figure 1. This is used to convert probabilities to stochastic streams. In this figure, X and R are Wbit wide inputs. R is a random number with uniform distribution which varies in each clock cycle. The output bit of the comparator is `1' when X > R and ‘0’ when X < R. therefore, the probability of having an output equal to `1' is X / 2W.
Figure 1: Probability to stochastic stream conversion. Once a stochastic stream of bits has been generated it must be used to perform mathematical operations such as multiplication and division of probabilities. Let Pa = Pr(ai=1) and Pb= Pr(bi=1) be the probabilities to be multiplied. The outcome, Pc, can be computed by an AND gate as shown in Figure 2 below.. Similarly, other Boolean operations e.g., NOT, XOR etc. can be implemented simply using basic logic gates.
Figure 2: Stochastic multiplication. Consider the JK flipflop shown in Figure 3 with input sequences of ai and bi representing the probabilities of Pa and Pb respectively. The output bit ci is equal to one with the probability of Pc and is equal to zero with the probability of 1Pc. A random output transition from 1 to 0 occurs with probability of 1  PcPa and the reverse transition occurs with the probability of PcPb. Since the expected occurrence of random transitions in both directions must be equal, we have Pc = Pa/(Pa + Pb). The resulting circuit, shown in Figure 4, although an approximation to Pa/Pb, matches the variable node operation we require for an errr correcting decoder..
Figure 3: Stochastic division. The stochastic representation of probabilities in the code graph results in lowcomplexity bitserial paritycheck and variable nodes. Let Pa = Pr(ai = 1) and Pb = Pr(bi = 1) be the probability of two input bits, ai and bi, in a degree3 check node. The output probability Pc is computed as Pc = Pa (1  Pb) + Pb (1  Pa). Similarly, the equality function in a degree3 variable node for inputs Pa and Pb is Pc = Pa Pb/(Pa Pb+ (1  Pa)(1Pb)). Figure 4 shows the resulting hardware structures. Note that the variable node in Figure 4(B) is in the hold state (i.e., c i= ci1), if the two input bits are not equal.
Figure 4: Parity check and variable nodes in stochastic decoders. In addition to simple variable and check node structures, stochastic computation also reduces the routing congestion problem because only one bit (per direction) is required to represent an edge between a paritycheck and a variable node. This implies that in a decoding round, the stochastic decoding proceeds by the variable and check nodes exchanging a bit (per direction) along each edge in the graph. We refer to these decoding rounds as decoding cycles (DCs) to highlight that they do not directly correspond to the iterations in conventional iterative decoding algorithms. Initial attempts to implement stochastic decoders using the circuits described above were not successful (except for some special cases as in [1], and these attempts still did not match the performance of conventional decoders). This is due to the sensitivity of stochastic decoding to the level of random switching activity (bit transition). This problem is especially crucial because the code graph has cycles. The latching problem refers to the case where cycles in the graph correlate messages such that a group of nodes are locked into a fixed state which is solely maintained by the correlated messages This problem can be worse at high SignaltoNoiseRatios (SNRs) because the received Loglikelihood ratios (LLRs) are large so that the corresponding probabilities approach 0 (or 1). In this situation, bits in stochastic sequences are mostly 0 (or 1), making random switching events very rare. Figure 5 illustrates the latching of two variable nodes, v1 and v2, into a fixed (hold) state for several DCs, which is forced by a 4cycle in the absence of enough switching activity. The latching problem causes huge performance loss for decoding LDPC codes. Previous attempts by other groups to tackle the latching problem were not successful. Our approach succeeds because it views the decoding as a relaxation procedure and is not concerned with reproducing the exact values of probabilities. We introduce two simple procedures which are together necessary for solving the latching problem. Figure 5. An example of latching within a 4cycle. Ingredients of the Proposed Solution 1. Rerandomizing Edge Memories The first component of our solution to the lockup problem is rerandomization by reordering the last few “good” bits generated at the variable nodes, i.e. those that were not generated from the hold state of the JK flip flop. We introduce Mbit shift registers, called edge memories (EMs) at each edge of the code graph. Each EM is updated only when the variable node is not in the hold state for that edge. If a hold state happens, a bit is randomly chosen from the EM of the edge and passed as the outgoing bit, this can be done by generating random addresses for EMs. Bittrue simulations show that we can share the random number generation methods for the input streams with no loss of performance. Using this updating scheme the random switching activity of stochastic messages in the code graph is increased because the chance of locking into a fixed state is reduced. This is because in a hold state, a bit is randomly chosen from those previous outputs of the variable node which are not produced in a hold state. 2. NoiseDependent Scaling The second component of our solution to the lockup problem is to scale the received values to increase the switching activity. The latching problem can be worse at high signaltonoise ratios (SNRs) due to the lack of switching activity. The idea of scaling channel LLRs is based on scaling received LLRs to increase switching activity in the decoder. Our solution scales channel LLRs by a factor which is proportional to the operating SNR. Because the scaling factor is proportional to the noise level, it ensures a similar level of switching activity for different ranges of SNRs. The scaled LLR, Si, for the ith symbol, yi, is calculated as Si = (a N0 / Y) L i = 4a yi / Y, where Y is a fixed maximum value of the received symbols and, a is a constant factor in which its value can be chosen based on the BER performance. The noise dependence of the LLR without scaling is cancelled by the noisedependent scaling factor resulting in a noiseindependent expression. This has the welcome sideeffect of eliminating the SNR estimation block from the receiver. Competing Technologies
The first LDPC decoder was reported in [2] in 2002 as a fully parallel multibit architecture. All of the nodes are directly implemented on the chip and connected by a large number of wires. The advantage of this technique is high throughput but the high speed comes at a steep price: large silicon area and high power dissipation. Additionally, the design of this chip required an unusual effort and required the development of custom computeraided design software to route the wires on the chip. This is not a commerciallyviable solution. For these reasons, this architecture has not been reconsidered in the 6 years since this publication. In comparison to this architecture, stochastic decoding shares the throughput advantage since it is also fully parallel. However, because stochastic decoding messages are only 1bit wide, the number of wires required is reduced dramatically and routing the wires can be done using conventional design methodologies. This has been verified by our synthesis results. The area of stochastic decoders is much smaller due to the ultralowcomplexity variable and check node hardware.
Because of the difficulties in implementing fullyparallel multibit decoders, most effort in LDPC decoding hardware both in research and commercial activities has focused on partially parallel decoders. In this technology, only a small number of hardware processing elements are implemented on the chip and are shared amongst the nodes of the graph to minimize silicon area. The drawback of this technique is that the throughput is significantly reduced. Power consumption is also high because of the data shuffling required between memory banks. This architecture works best with speciallyconstructed codes that are designed to reduce collisions between accesses to the memory banks. In contrast, stochastic decoders are fully parallel, do not require internal memory and have much greater throughput. They are not restricted to any particular code structure. Stochastic decoders directly attack the area and routing problems by using simple node hardware enabling us to integrate all of the nodes onto a single chip.
To reduce the routing congestion problem, bitserial decoders are fullyparallel decoders that send one bit of a multibit message at a time over a single wire. This reduces the routing complexity significantly but the multi bit messages must be stored and parallelized and manipulated using multibit ALU hardware in both the check and equality nodes so that the silicon area required is still too large. Stochastic decoder nodes are much simpler and when they converge the switching activity on the wires decreases drastically as the stochastic stream becomes a train of all ‘0’s or all ‘1’s reducing the power consumption of the decoder. In contrast, bitserial decoders always consume power even when the decoder has converged.
To address the above concerns, decoders built using analog circuits were developed in the research community. As in stochastic decoding, they use a very simple node circuitry, and only one wire per message. However, analog decoders suffer several obstacles to commercialization:
Stochastic decoders use the standard digital design flow and can be ported to new technologies by computeraided design software with little modification. Analog decoders tend to be designed to operate at the highest speed achievable in a given process to provide processing margin and may consume more power than is required. If a communication protocol offers variable throughput then a stochastic decoder may be clocked more slowly to lower the power consumption. A Stochastic Decoder for 10Gb Ethernet We have applied the technique of stochastic decoding to the specified algorithm for 10 Gb Ethernet (10 GBaseT). Our decoder provides excellent decoding performance as shown in Figure 6 in which we compare simulations of the decoder circuit to a high precision computation using the same input data. Computation of the SumProduct algorithm for 32 iterations using high precision 64 bit arithmetic would be prohibitively expensive, our stochastic decoder implementation provides less than 0.2 dB loss in performance at full line rate.
Figure 6: Stochastic decoding performance of LDPC code for 10 Gbit Ethernet. Conclusions We have described the principle of stochastic computation and demonstrated its advantages in performance, circuit size, and power consumption when applied to LDPC decoding. Properly designed it can produce excellent results with few of the drawbacks of the simplifying design techniques used in most LDPC decoders. References [1] W. J. Gross, V. Gaudet, and A. Milner, “Stochastic implementation of LDPC decoders,” Proc. 39th Asilomar Conf. on Signals, Systems, and Computers, Nov. 2005. [2] A. J. Blanksby and C. J. Howland, “A 690mW 1Gb/s 1024b Rate1/2 LowDensity ParityCheck Decoder,” IEEE Journal of SolidState Circuits, Vol. 37, No. 3. pp. 404412, March 2002. Other important Works [1] S. Sharifi Tehrani, W. J. Gross, and S. Mannor, “Stochastic decoding of LDPC Codes,” IEEE Communications Letters, 10(10):716–718, Oct. 2006. [2] S. Sharifi Tehrani, S. Mannor, and W. J. Gross, “Stochastic decoding of LDPC Codes,” To appear in the IEEE International Symposium on Multiple Valued Logic, May 2007. [3] T. Richardson and R. Urbanke, “The capacity of lowdensity paritycheck codes under message passing decoding,” IEEE Transactions on Information Theory, vol. 47, pp. 599–618, February 2001. [4] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Kaufman, 1988. [5] B. Gaines, Advances in Information Systems Science, Chapter 2, pages 37172, Plenum, New York, 1969. [6] R. G. Gallager. Low Density Parity Check Codes. MIT Press, Cambridge MA, 1963. [7] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near ShannonLimit ErrorCorrecting Codes: Turbo Codes,” Proc. IEEE Int. Conf. on Communications, pp. 10641070, May 1993. [8] F. R. Kschischang, B. Frey, and H.A. Loeliger, “Factor Graphs and the SumProduct Algorithm,” IEEE Trans. Information Theory, Vol. 47, No. 2, pp. 498519, February 2001. [96] B. Brown and H. Card. “Stochastic neural computation I: Computational elements,” IEEE Trans. on Computers, 50(9):891–905, Sept. 2001. [10] V. Gaudet and A. Rapley, “Iterative decoding using stochastic computation,” Electron. Letters, 39(3):299–301, Feb. 2003. 
Home  Feedback  Register  Site Map 
All material on this site Copyright © 2017 Design And Reuse S.A. All rights reserved. 