PRBS+PISO+SIPO+Reed Solomon Coder and Decoder - Assignment Example

Engineering and Construction PRBS+PISO+SIPO+Reed Solomon r & De r Question Pseudo-Random binary sequence (PRBS) Description of the Design PRBS is an autocorrelation function of a binary sequence. A binary sequence on N bits which begins from A0, A1, A2…A (N – 1). Binary sequence consist of M, as the sum ∑Aj binary ones and N – M binary zeros, where j=0, 1, 2 …N-1. PRBS Equation The PRBS autocorrelation function is presented as: C (v) = ∑Aj A (j + v), where j = 0, 1, 2…N – 1. In the function, the duty cycle (C) is calculated as: C = (M – 1) / (N – 1) A PRBS is referred to as pseudorandom because it is deterministic but apparently random since the values of A j (1s) elements are not dependent on the values of other existing binary elements. It is possible to stretch a PRBS sequence to infinity by creating an iteration of its sequence after every N element. It differs from other types of infinite sequences such as radioactive decay (Katz & Boriello, 2005) and (Lala, 1996). Unlike the optimal (maximum) length sequence, the Pseudo-Random Binary Sequence is more general (Geisel, 1990). PRBS sequences find their application in the field of information management such as telecommunication, data encryption, system simulation, statistical correlation methods and the spectroscopy of flight times (Awschalom, Loss & Samarth, 2002). Practical Application The practical process for generating the Pseudorandom binary sequences can be implemented through shift registers that can provide linear feedbacks (Horowitz and Hill, 1989). Examples of the sequences that generate polynomials are stated below: PRBS7 = X7 + X6 + 1 PRBS15 = X15 + X14 + 1 PRBS23 = X23 + X18 + 1 PRBS31 = X31 + X28 + 1 PRBS39 = X39 + X34 + 1 Pseudo-random binary sequence are essential in the practical data randomization through the operation of exclusive OR. Question 2: Parallel Input Serial Output (PISO) Description of the design of PISO The PISO shift register (Parallel-in to Serial-out) operates in an opposite direction as the SIPO register. The shift register receives data in parallel form. All the inputs of the data bits enter the parallel input pins simultaneously. The parallel pins are labeled as P1, P2, P3 and P4in the PISO shift register (Hetzel, 1988). The reading of the input data then takes place in a sequential order inside the PISO register in a shift-right mode (Maini, 2007). This takes place at the Q data output pins of the register. Q represents the available data at the input pins P1 to P4. The output of the data comes out 1 bit each time on every clock cycle (Crowell & Press, 2002). As the input is in parallel format, the output of the data at Q is in serial format. Fundamentally, in the PISO system, there is no need of generating a clock pulse (Brown et al, 1992). The clock pulse is already present in the register for parallel loading. However, during the unloading of the data, the register requires generation of 4 clock pulses (Predko and Predko, 2004). Figure 1: 4-bit PISO Shift Register The PISO shift register transforms parallel input data into a serial output data whose size fully depends on the size of the input signals. For example, the input can be an 8 - bit data that can be converted into serial formats (Zvi & Niraj, 2009). It multiplexes multiple input data into one serial stream of output that can move directly to a computer or flow in a communication line. Equation The equation for the PISO shift register is: P 0 + P1 + P2 + P3 + Clock = Q Question 3: Serial Input Parallel Output (SIPO) Description of the design of SIPO In the operation of the SIPO shift registers, the assumption is that all the flip-flops from FFA to FFD have just undergone resetting to clear the input lines and all outputs data from QA to QD have been reset to logic level zero (0); hence have no parallel output data. Figure 2: 4 - Bit SIPO Shift Register If an input of logic high (1) connects to the input pin of the Flip flop FFA and proceeds on the clock pulse, the output data of the FFA flipflop and the QA output data are set to high (logic 1). According to Hickey (2008), all the other outputs QB, QC and QD remain at logic low (0). In this assumption, Vasyukevich (2009) argues that data input pin for the flip-flop FFA returns to LOW (logic 0) and generates one data pulse 0-1-0. The second clock pulse of the shift register converts the output of the flipflop FFA to low (logic 0). The output data for flip-flop FFB and that of QB changes from binary HIGH to logic 1 because its D input has the logic 1 from the output line QA, according to Miller (2011). The register has thus shifted the logic “1″ or moved it to the right direction since it is at the output pin QA. As the third clock pulse comes in, the logic 1 value shifts to the output pin of flip-flop FFC (QC). The sequence continues until the fifth clock pulse arrives and sets every output from QA to QD back to logic 0 (Null & Lobur, 2006) Equation The equation of the SIPO shift register is: D = QA + QB + QC + QD + CLK Question 4: Reed Solomon Coder (RS coder) Description of the Design of RS coder The RS (Reed–Solomon) coders are registers that use the Reed – Solomon codes, which are the non-binary cyclic codes for the correction of error. The codes were designed in such a way that they can detect and correct multiple errors arising from the random symbols (Bostock, 1988). The codes check error when t random check symbols are selected and added to the data (Ceruzzi, 2012). The Reed Solomon codes are able to detect a maximum combination of t erroneous check symbols or do correction of up to half of the symbols (Katz, 1994). Further to that, the Reed Solomon codes apply as error detecting and correcting codes for multi-burst bit-error. If a sequence contains b + 1 bit errors consecutively, a maximum of two symbols can be affected if the symbols are of size B. In the Reed–Solomon (RS) coder, the source symbols appear as the coefficients of P(x), a polynomial function over a finite limited. The designers of Reed Solomon Coding technique had an original idea to over sample the P(x) polynomial function at n different points where n > k and develop n symbols of the code originating from k source symbols (Lehtonen & Laihom, 2009). The codes transmit the sample points, and recover the initial message using interpolation methods in the receiver end (Leens, 2010). In the modern age, the RS codes exist as cyclic codes, using coding symbols generated from a set of coefficients of the polynomial function P(x) developed as a product of the p(x) and a cyclic-generator polynomial function. Reed–Solomon codes are applicable in the communication and consumer digital electronic systems such as CDs, Blue ray disc, DVDs systems and the methods of transmitting data including WiMAX, DSL; DVB broadcast system and RAID 6 computer applications (Brown & Vranesic, 2009). Reed–Solomon codes are the main elements of a compact disc (CD). The CD has two layers of RS codes, between which lies the Cross-Interleaved RS Coding (Chan and Lim, 2008). The Reed Solomon Codes are classified under several codes such as the cyclic code, polynomial code, linear – block code and the BCH codes (Kleitz, 2002). The RS code is the highest level of the coding standard in the hierarchy of the entire set of codes. RS error correcting technique is also applicable in the management of archive files majorly posted along with multimedia files shared on the Usenet protocols (Bardell, McAnney and Savir, 1987). It also applies in the distributed online portal Wuala in the process of splitting up files into the required blocks (Witte, 2002). Equation There are many equations depending on the parameters being measured and assessed. Order of the finite field (q) Block length is calculated as n = q − 1 Message length is denoted by k Distance = n − k + 1 Notation [n, k, n − k + 1] q – code The major equation of the Reed Solomon code C is defined as shown below: C = [P (a1), p (a2) ….P (an)] (Beker & Piper, 1982) In the function, P is the polynomial over a function of degree less than k. The relative distance is calculated as: D = d / n, where d = n – k + 1. Question 5: Reed Solomon Decoder (RS decoder) Description of the design of RS decoder According to Tocci (2006), the Reed Solomon decoder does the processing of every block and tries to correct the errors with an aim of recovering the initial data. The number of errors and the types that it can correct is dependent on the properties of the Reed Solomon code being implemented. The RS codes sub components of the BCH codes. They codes exist in form of linear blocks stated or defined as RS (n, k) having s - bit symbols (Ceruzzi, 2012). The structure of the linear block is demonstrated below. Figure 3: Linear Block of the Reed Solomon Code This implies that the coder uses k symbols of the data from the s bits and adds each of the parity bit symbols to form a code word of n symbols. Each of the parity symbols has s bits. Reed-Solomon decoder is able to correct a maximum of t symbols. It contain an amount of errors in code word with n – k = 2t. The diagram below demonstrates a general structure of the systematic code of the Reed - Solomon codeword. The data is left unaltered and while its parity symbols are linked. Figure 3: Systematic Code The Reed Solomon algebra for decoding is able to correct the errors and erasures. An erasure shows up where the erroneous symbol is in a specific position (Lu, Willi & Serge, 2005). The RS decoder therefore, corrects a maximum of t errors and a maximum of 2t erasures (Brown & Vranesic, 2009). The erasure information is provided by the demodulator in an electronic communication channel. The demodulator serves the purpose of flagging the incoming symbols, which it suspects to be containing errors. Decoding of code words causes three possible results (Savant, Roden & Carpenter, 1991). Result 1 If 2t > 2s + r (r erasures and s errors) the initial communicated codeword will be restored. Result 2 The Reed Solomon Decoder will discover that it is not able to recover its original codeword and indicate the fact about the erasures and errors. Result 3 The Reed Solomon decoder will do misreading, hence recovers wrong codeword with any indicator (Barkam, Biham & Keller, 2008). The possibility of any of the events is dependent on the Reed Solomon code and the number of errors available. Use of Euclidean Algorithm Another iterative approach to the calculation of the error locating polynomial is based on the Euclidean Algorithm. t = the number of parity bits R0 = xt S-0 = syndrome polynomial A-0 = 1 B-0 = 0 i = 0 while deg of S-i > (t / 2) or deg of S-i = (t / 2) Q = R-i / S-i Si+1 = R-i – Q * S-i = R-i modulo S-i Ai+1 = Q*A-i + B-i Ri+1 = S-i Bi+1 = A-i i = i + 1 Λ(x) = A-i / A-i (0) Ω(x) = (–1) deg A-i * S-i / A-i (0) A-i (0) is the minimum significant term of Ai and is a constant. Equation There are many equations of Reed Solomon decoder as demonstrated in the Eucladean Algorithm. The general equation for error detection is controlled by the condition below 2t > 2s + r References Bardell, P. H., McAnney, W. H. and Savir, J. (1987). "Built-In Test for VLSI: Pseudorandom Techniques", New York: John Wiley & Sons. Barkam, E, Biham, E. & Keller, N (2008), "Instant Cipher text-Only Cryptanalysis of GSM Encrypted Communication", Journal of Cryptology 21 (3): 32–42. Beker, H. & Piper, F. (1982). Cipher Systems: The Protection of Communications. Wiley-Interscience. p. 22. Brown, S. & Vranesic, Z. (2009). Fundamentals of Digital Logic with VHDL Design. 3rd ed. New York, N.Y.: Mc Graw Hill. Ceruzzi, P. E. (2012). Computing (MIT Press Essential Knowledge). MIT Press. Chan, Y. K and Lim, S. Y. (2008). Progress In Electromagnetics Research B, Vol. 1, 269–290,"Synthetic Aperture Radar (SAR) Signal Generation, Faculty of Engineering & Technology, Multimedia University, Jalan Ayer Keroh Lama, Bukit Beruang, Melaka 75450, Malaysia. Crowell, G. & Press, R. (2002). "Using Scan Based Techniques for Fault Isolation in Logic Devices". icroelectronics Failure Analysis. pp. 32–38. Geisel, W. A. (1990), Tutorial on Reed–Solomon Error Correction Coding, Technical Memorandum, NASA, TM-102162. Hetzel, P. (1988). "Time dissemination via the LF transmitter DCF77 using a pseudo-random phase-shift keying of the carrier". 2nd European Frequency and Time Forum. Neuchâtel. pp. 35–36. Horowitz, P and Hill, W. (1989). The Art of Electronics 2nd Ed. Cambridge University Press, Cambridge. Katz, R. & Boriello, G. (2005). Contemporary Logic Design. 2nd ed. Prentice Hall. 2005. Katz, R. H. (1994). Contemporary Logic Design, The Benjamin/Cummings Publishing Company, 1994. Kleitz, W. (2002). Digital and Microprocessor Fundamentals: Theory and Application. 4th ed. Upper Saddler Reviver, NJ: Pearson/Prentice Hall. Lala, P. K. (1996). Practical Digital Logic Design and Testing, Prentice Hall, 1996. Leens, F. (2010). "The Digital Pattern Generator - An essential instrument for digital system development", Byte Paradigm. Lehtonen, E. & Laihom, M. (2009). "Stateful implication logic with memristors", Proceedings of the 2009 IEEE/ACM International Symposium on Nanoscale Architectures IEEE Computer Society Washington, DC, USA. Lu, Y, Willi, M., & Serge, V. (2005). "The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption". Crypto 2005 (Santa Barbara, California, USA) 3621: 97–117. Maini. A.K. (2007). Digital Electronics Principals, Devices and Applications. Chichester, England.: Jonh Wiley & Sons Ltd. Miller, V. (2011). Understanding digital culture. "Convergence and the contemporary media experience". London: Sage Publications. Null, L. & Lobur, J. (2006). The essentials of computer organization and architecture. Jones & Bartlett Publishers. p. 21. Tocci, R. (2006). Digital Systems: Principles and Applications (10th Edition). Prentice Hall. Vasyukevich, V. O. (2009). Asynchronous logic elements. Venjunction and sequention — p18. Witte, R. A. (2002). "Electronic Test Instruments: Analog and Digital Measurements, 2nd Edition", Prentice Hall. Zvi K. & Niraj K. J. (2009). Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. Hickey, A. R. (2008). "Crazy Ant Invasion Frying Computer Equipment. Predko, M and Predko, M. (2004). Digital electronics demystified, McGraw-Hill. Savant, C. J., Roden, M. & Carpenter, G. (1991). "Electronic Design: Circuits and Systems". Awschalom, D.D., Loss, D. & Samarth, N. (2002). Semiconductor Spintronics and Quantum Computation. Berlin, Germany: Springer-Verlag. Bostock, G. (1988). Programmable logic devices: technology and applications. New York: McGraw-Hill. ISBN 978-0-07-006611-3. Retrieved 28 November 2012. Brown, S. D., Francis, R.J., Rose, J, Vranesic, Z. G. (1992). Field Programmable Gate Arrays. Boston, MA: Kluwer Academic Publishers. Read More