La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

LEADER'S GUIDE

10 pages
  • cours - matière potentielle : counselor
  • cours - matière potentielle : culture of trust
  • cours - matière potentielle : teachers
  • expression écrite
  • cours - matière potentielle : rules
  • cours - matière potentielle : victims
  • cours - matière potentielle : bullies
  • cours - matière potentielle : with lower levels
  • cours - matière potentielle : communities
  • cours - matière potentielle : action
  • cours - matière potentielle : violence
  • cours - matière potentielle : playground
  • cours - matière potentielle : administrators
  • cours - matière potentielle : support staff
  • cours - matière potentielle : pride
  • cours - matière potentielle : districts
  • cours - matière potentielle : responsible choices
  • cours - matière potentielle : community
  • cours - matière potentielle : norms about violence
  • cours - matière potentielle : through follow
  • cours - matière potentielle : bus
  • cours - matière potentielle : years
LEADER'S GUIDE STEPPING UP TO BULLYING Lesson 1 Dealing with Bullies Lesson 2 Standing Up, Not Standing By Lesson 3 Reaching Out to Victims Lesson 4 Building Bully-Free Schools/Communities
  • protect victims from retaliation
  • lesson through follow
  • zazi
  • positive ways
  • peer education
  • victims
  • discussion questions
  • discussion of questions
  • solutions
  • school
  • students
Voir plus Voir moins
Cyclic Redundancy Check Computation Using TI - DSP
EE201A Class Presentation
Ram Kumar Vijay Raghunathan
Outline
Intro. to Coding and Galois Field
Theory of Linear Cyclic Codes
Computational requirements of CRC
Advantages of using DSPs for CRC
1
Introduction
Application domain: Digital transmission
Channels are noisy Errors are introduced into transmitted data
Need error detection and correction
Coding provides means to achieve it
Error Correction Coding
Basic idea: Introduce redundancy
Two main types Block codes Convolutional codes
Cyclic Redundancy Check (CRC) codes Type of cyclic block codes
2
Coding Theory Behind CRC
Block code Set of fixed length code words Length of code word isn Galois Field (2): Code word symbols are binary n code words2 possible Message: k bits k 2 message words k Choose 2 code words and map them to message words This is an <n,k> code
Coding Theory Behind CRC (Contd.)
“d” is the min. Hamming distance between two code words <n,k> code can detect (d-1) errors and correct (d-1)/2 errors Linear block codes: Addition of two code vectors results in code vector Cyclic codes: Subset of linear block codes Cyclic shift of code vector results in code vector
3
CRC Computation
Notation Message Vectorm= (m ,m ……m ,m ) 0 1 k-2 k-1 k-2 k-1 m xx + + …… m Message Polynomial: m(x) = m 0 k-2 k-1 g(x): Generator Polynomial (n-k bits) C(x): Code word Polynomial (n bits) c(x) = m(x) . g(x) n-k Equivalently, c(x) = x m(x) + r(x) n-k m(x) by g(x)r(x) is remainder of x r(x) contains the actual CRC bits
Example of <7,4> CRC Code
3 (1101)g(x) = 1 + x + x 3 m(x) = 1 + x (1001) 3 r(x) = x m(x) mod g(x) 3 6 3 i.e., r(x) = (x + x ) % (1 + x + x ) 2 = (x + x ) = (011) 2 3 6 Therefore, c(x) = x + x + x + x =0111001
4
Types of CRC Codes
Differ in value of g(x)
Bitwise algo. for CRC Calculation
Linear Feedback Shift Register (LFSR)
5
TMS320C54x Arch. Features
16 bit fixed point DSP 40-bit Arithmetical and Logical Unit Two 40-bit accumulators (A and B) Efficient memory addressing modes Multiple bus structure Barrel shifter
Bitwise CRC: SW Implementation
CRC bits are stored in CRC register Steps: CRC <- 0 If MSB of CRC is equal to 1 then Shift in next message bit XOR the CRC register with Generator else Shift in next message bit Repeat above step till all bits of augmented message have been shifted in
6
Bit-wise CRC routine on DSP
Standard Lookup Table Algo.
α Maintain a look-up table of 2 elements of (n-k) bits
Steps 1.CRC <- 0 ,i.e. (r ,……,r ) n-k-1 0 2.XOR theαinput bits with the CRC register contents shifted right by n-k-αbits, i.e. XOR with (r ,……, r ) n-k-1 n-k-α 3.Find the corresponding value in the lookup table and XOR the CRC register content shifted left byαbits, i.e. XOR with (r ,……,r ) This is the new CRC value α-1 0 4.Repeat steps 2 and 3 till end of message
7
Table lookup routine on DSP
Advantages of using DSP
Bit level manipulation instructions sftl: Shift accumulator logically This instruction logically shifts src and stores the result in dst or src Takes 1 cycle to execute stl: Store accumulator low in memory This instruction stores the low part of src (bits 15–0) in data-memory location Smem Takes 1 or 2 clock cycles to execute
8
Advantages of using DSP (contd.)
Bit manipulation instr. xor: Bitwise excl. or of two registers Block processing instruction rptb: Block Repeat Repeats a block of instr. the number of times specified by the memory-mapped block-repeat counter (BRC). BRC must be loaded before the execution of this instr. Leads to compact code size
CRC-32 Implementation
9
Conclusions
Coding is necessary due to error prone nature of channel Digital trans.: Requires Galois Field (2) arithmetic Bit manipulation instr. costly in general purpose processors DSP provides special instructions for efficient implementation
References
TI Application Manual: SPRA530 (CRC computation: An implementation using the TMS320C54X) TI Application Manual: SPRA686 (Reed Solomon Decoder: TMS320C64X implementation) (Not talked about today) Digital Communications, John G. Proakis EE231E: Prof. Rick Wesel’s course on Channel Coding
10