source: caseStudy_Huffmann/huffmann/huff_synchro/huff_synchro.v

Last change on this file was 105, checked in by cecile, 14 years ago

Hufmann case study
File size: 7.4 KB
RevLine 
[105]1// Model of connected Huffman encoder and decoder.
2// The alphabet consists of the uppercase letters and the space.
3// The Huffman tree used by encoder and decoder is shown below.
4// All left branches are labeled 0, and all right branches are labeled 1.
5//
6// +-------------( )---------------+
7// | |
8// | |
9// +-------( )------+ +------( )-----+
10// | | | |
11// | | | |
12// +----( )----+ ( ) +--( )--+ ( )
13// | | / \ | | / \
14// | | | | | | | |
15// +--( )--+ ( ) [E] ( ) ( ) ( ) [ ] ( )
16// | | / \ / \ / \ / \ / \
17// | | | | | | | | | | | |
18// ( ) ( ) [S] ( ) ( ) [A] [I] [O] [R] [N] ( ) [T]
19// / \ / \ / \ / \ / \
20// | | | | | | | | | |
21// [U] [P] [F] [C] ( ) [L] [H] ( ) [D] ( )
22// / \ / \ / \
23// | | | | | |
24// +----( ) [W] [G] [Y] ( ) [M]
25// | \ / \
26// | | | |
27// ( ) ( ) [B] [V]
28// / \ / \
29// | | | |
30// [Q] ( ) [K] [X]
31// / \
32// | |
33// [Z] [J]
34//
35// As an example, the code of W is 001101.
36//
37// This tree is based on the following assumed frequencies.
38//
39// E 130 T 93 N 78 R 77 I 74 O 74 A 73 S 63 D 44
40// H 35 L 35 C 30 F 28 P 27 U 27 M 25 Y 19 G 16
41// W 16 V 13 B 9 X 5 K 3 Q 3 J 2 Z 1
42//
43// That is, it is assumed that there are 130 Es for every thousand letters.
44// It is further assumed that there are 182 spaces for every 1000 letters.
45//
46// The encoder retrieves the code for each symbol from a map, and shifts it
47// out one bit at the time. The decoder is a finite state machine whose
48// state transition graph is obtained from the tree by adding acs from the
49// leaves back to the top of the tree. (To the second level nodes to be
50// precise.) Each node uses ten bits for its encoding. The code of the root
51// is 0. If a state is not a leaf of the tree, and its encoding is n, then
52// the encodings of its two children are 2n+1 and 2n+2.
53
54// Author: Fabio Somenzi <Fabio@Colorado.EDU>
55
56module main(clk, addr,plain);
57 input clk;
58 input [4:0] addr;
59
60
61 wire cipher;
62 output [7:0] plain;
63 wire[7:0] character;
64
65 huffmanEnc encoder (clk, addr, cipher, character,start);
66
67 huffmanDec decoder (clk, cipher, plain,start);
68
69 // Latch data that we want to refer to in properties.
70 /* reg ci;
71 reg [7:0] ch;
72
73 initial begin
74 ci = 0;
75 ch = 0;
76 end
77
78 always @ (posedge clk) begin
79 ci = cipher;
80 ch = character;
81 end
82*/
83endmodule // main
84
85
86module huffmanEnc (clk, addr, cipher, character,start);
87 input clk;
88 input [4:0] addr;
89 output cipher;
90 output [7:0] character;
91 output start;
92
93 reg start;
94 reg [7:0] character;
95
96 // This function is the map from symbols (ASCII space and uppercase
97 // letters) to codes. Each code consists of from 3 to 9 bits.
98 // Since the codes are of variable length, an additional
99 // bit is used to mark the end of the symbol. This bit is the
100 // leftmost 1. The code is sent out LSB first; hence, it is reversed
101 // in this map. For instance, 0000010100 (the entry of the map for S)
102 // says that the code for S is 0010.
103 function [9:0] code;
104 input [7:0] c;
105 begin: _code
106 case (c)
107 69: code = 10'b0000001010; // E
108 32: code = 10'b0000001011; // space
109 83: code = 10'b0000010100; // S
110 65: code = 10'b0000011110; // A
111 73: code = 10'b0000010001; // I
112 79: code = 10'b0000011001; // O
113 82: code = 10'b0000010101; // R
114 78: code = 10'b0000011101; // N
115 84: code = 10'b0000011111; // T
116 85: code = 10'b0000100000; // U
117 80: code = 10'b0000110000; // P
118 70: code = 10'b0000101000; // F
119 67: code = 10'b0000111000; // C
120 76: code = 10'b0000111100; // L
121 72: code = 10'b0000100110; // H
122 68: code = 10'b0000100111; // D
123 87: code = 10'b0001101100; // W
124 71: code = 10'b0001010110; // G
125 89: code = 10'b0001110110; // Y
126 77: code = 10'b0001110111; // M
127 66: code = 10'b0010010111; // B
128 86: code = 10'b0011010111; // V
129 81: code = 10'b0100001100; // Q
130 75: code = 10'b0101001100; // K
131 88: code = 10'b0111001100; // X
132 90: code = 10'b1010001100; // Z
133 74: code = 10'b1110001100; // J
134 default: code = 10'b0;
135 endcase // case(character)
136 end
137 endfunction // code
138
139 // This function supplies the ASCII codes of the symbols.
140 function [7:0] ROM;
141 input [4:0] address;
142 begin: _ROM
143 if (address < 26)
144 ROM = 65 + {3'b0, address};
145 else
146 ROM = 32;
147 end
148 endfunction // ROM
149
150 reg [9:0] shiftreg;
151
152 initial begin
153 character = 0;
154 shiftreg = 0;
155 start = 0;
156 end
157
158 always @ (posedge clk)
159 begin
160 if (shiftreg[9:1] <= 1) // added by Cecile 24.06.11
161 begin
162 character = ROM(addr);
163 shiftreg = code(character); // load a new code
164 start = 1;
165 end
166 else
167 begin
168 shiftreg = {1'b0, shiftreg[9:1]}; // shift right
169 start = 0;
170 end
171 end
172
173 assign cipher = shiftreg[0];
174
175endmodule // huffmanEnc
176
177
178// The output plain is 0 except for one clock cycle when a character has
179// been decoded.
180module huffmanDec (clk,cipher,plain,start);
181 input clk;
182 input cipher;
183 output [7:0] plain;
184 input start;
185
186 reg [9:0] state;
187
188 wire leaf;
189 wire [7:0] character;
190
191 initial state = 0;
192
193 // This function maps states to characters. All non-leaf states are
194 // mapped to NUL. The leaf states are mapped to the ASCII code of the
195 // corresponding symbol.
196 function [7:0] map;
197 input [9:0] state;
198 begin: _map
199 case (state)
200 9: map = 69; // E
201 13: map = 32; // space
202 17: map = 83; // S
203 22: map = 65; // A
204 23: map = 73; // I
205 24: map = 79; // O
206 25: map = 82; // R
207 26: map = 78; // N
208 30: map = 84; // T
209 31: map = 85; // U
210 32: map = 80; // P
211 33: map = 70; // F
212 34: map = 67; // C
213 38: map = 76; // L
214 43: map = 72; // H
215 59: map = 68; // D
216 76: map = 87; // W
217 89: map = 71; // G
218 90: map = 89; // Y
219 122: map = 77; // M
220 243: map = 66; // B
221 244: map = 86; // V
222 303: map = 81; // Q
223 305: map = 75; // K
224 306: map = 88; // X
225 609: map = 90; // Z
226 610: map = 74; // J
227 default: map = 0;
228 endcase // case(state)
229 end // block: _map
230 endfunction // map
231
232 assign plain = map(state);
233 assign leaf = plain != 0;
234
235 always @ (posedge clk) begin
236 state = ((leaf||start) ? 0 : {state[8:0],1'b0}) + (cipher ? 2 : 1);
237 end
238
239endmodule // huffmanDec
Note: See TracBrowser for help on using the repository browser.