source: caseStudy_Huffmann/huffmann/huff_reset/huff_reset1.v @ 106

Last change on this file since 106 was 105, checked in by cecile, 12 years ago

Hufmann case study
File size: 7.9 KB
Line 
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        wire val;
60        wire ok;
61
62    wire  cipher;
63    wire [7:0] character;
64    output[7:0] plain;
65
66    huffmanEnc encoder (clk,addr,cipher,character,ok,val);
67
68    huffmanDec decoder (clk,cipher,plain,ok,val);
69
70    // Latch data that we want to refer to in properties.
71   /*
72    reg        ci;
73    reg [7:0]  ch;
74
75    initial begin
76        ci = 0;
77        ch = 0;
78    end
79
80    always @ (posedge clk) begin
81        ci = cipher;
82        ch = character;
83    end
84*/
85endmodule // main
86
87
88module huffmanEnc (clk, addr, cipher, character,ok,val);
89    input        clk;
90    input [4:0]  addr;
91    input        ok;
92    output       val;
93    output       cipher;
94    output [7:0] character;
95
96    reg [7:0]    character;
97
98    // This function is the map from symbols (ASCII space and uppercase
99    // letters) to codes.  Each code consists of from 3 to 9 bits.
100    // Since the codes are of variable length, an additional
101    // bit is used to mark the end of the symbol.  This bit is the
102    // leftmost 1.  The code is sent out LSB first; hence, it is reversed
103    // in this map.  For instance, 0000010100 (the entry of the map for S)
104    // says that the code for S is 0010.
105    function [9:0] code;
106        input [7:0] c;
107        begin: _code
108            case (c)
109              69: code = 10'b0000001010; // E
110              32: code = 10'b0000001011; // space
111              83: code = 10'b0000010100; // S
112              65: code = 10'b0000011110; // A
113              73: code = 10'b0000010001; // I
114              79: code = 10'b0000011001; // O
115              82: code = 10'b0000010101; // R
116              78: code = 10'b0000011101; // N
117              84: code = 10'b0000011111; // T
118              85: code = 10'b0000100000; // U
119              80: code = 10'b0000110000; // P
120              70: code = 10'b0000101000; // F
121              67: code = 10'b0000111000; // C
122              76: code = 10'b0000111100; // L
123              72: code = 10'b0000100110; // H
124              68: code = 10'b0000100111; // D
125              87: code = 10'b0001101100; // W
126              71: code = 10'b0001010110; // G
127              89: code = 10'b0001110110; // Y
128              77: code = 10'b0001110111; // M
129              66: code = 10'b0010010111; // B
130              86: code = 10'b0011010111; // V
131              81: code = 10'b0100001100; // Q
132              75: code = 10'b0101001100; // K
133              88: code = 10'b0111001100; // X
134              90: code = 10'b1010001100; // Z
135              74: code = 10'b1110001100; // J
136              default: code = 10'b0;
137            endcase // case(character)
138        end
139    endfunction // code
140
141    // This function supplies the ASCII codes of the symbols.
142    function [7:0] ROM;
143        input [4:0] address;
144        begin: _ROM
145            if (address < 26)
146              ROM = 65 + {3'b0, address};
147            else
148              ROM = 32;
149        end
150    endfunction // ROM
151   
152    function cpt;
153        input [3:0] cpts;
154        begin: _cpt
155            if (cpts==5)
156              cpt=1;
157            else
158              cpt=0;
159        end
160    endfunction //val       
161
162    reg [9:0] shiftreg;
163    reg [3:0] count;
164    wire      val;
165    initial begin
166        character = ROM(addr);
167        shiftreg = code(character);
168        count=0;
169    end
170
171    always @ (posedge clk) begin 
172       if ((shiftreg[9:1] == 1)&&(count!=5)) begin
173            count=count+1;
174            character = ROM(addr);
175            shiftreg = code(character); // load a new code
176        end else if ((count>=5)&&(ok==1)) begin
177            count=0;
178            character = ROM(addr);
179            shiftreg = code(character);   
180        end else if ((count>=5)&&(ok!=1)) begin
181            count=count;
182        end else begin
183            shiftreg = {1'b0, shiftreg[9:1]}; // shift right
184        end 
185    end
186    assign val=cpt(count);
187    assign cipher = shiftreg[0];
188
189endmodule // huffmanEnc
190
191
192// The output plain is 0 except for one clock cycle when a character has
193// been decoded.
194module huffmanDec (clk,cipher,plain,ok,val);
195    input        clk;
196    input        cipher;
197    input        val;
198    output       ok;
199    output [7:0] plain;
200
201    reg [9:0]    state;
202    reg         ok;
203    wire         leaf;
204    wire [7:0]   character;
205
206    initial state = 0;
207    initial ok = 0;
208
209    // This function maps states to characters.  All non-leaf states are
210    // mapped to NUL.  The leaf states are mapped to the ASCII code of the
211    // corresponding symbol.
212    function [7:0] map;
213        input [9:0] state;
214        begin: _map
215            case (state)
216                9: map = 69; // E
217               13: map = 32; // space
218               17: map = 83; // S
219               22: map = 65; // A
220               23: map = 73; // I
221               24: map = 79; // O
222               25: map = 82; // R
223               26: map = 78; // N
224               30: map = 84; // T
225               31: map = 85; // U
226               32: map = 80; // P
227               33: map = 70; // F
228               34: map = 67; // C
229               38: map = 76; // L
230               43: map = 72; // H
231               59: map = 68; // D
232               76: map = 87; // W
233               89: map = 71; // G
234               90: map = 89; // Y
235              122: map = 77; // M
236              243: map = 66; // B
237              244: map = 86; // V
238              303: map = 81; // Q
239              305: map = 75; // K
240              306: map = 88; // X
241              609: map = 90; // Z
242              610: map = 74; // J
243              default: map = 0;
244            endcase // case(state)
245        end // block: _map
246    endfunction // map
247
248    assign plain = map(state);
249    assign leaf = plain != 0;
250
251    always @ (posedge clk) begin
252        state = (val ? 0 : ((leaf ? 0 : {state[8:0],1'b0}) + (cipher ? 2 : 1)));
253        ok = val;
254    end
255
256endmodule // huffmanDec
Note: See TracBrowser for help on using the repository browser.