source: caseStudy_Huffmann/huffmann/huff_reset/huff_reset2.v

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

Hufmann case study

File size: 8.2 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
60    wire  cipher;
61    wire [7:0] character;
62    output [7:0] plain;
63        wire val,ok;
64
65    huffmanEnc encoder (clk,addr,cipher,character,ok,val);
66
67    huffmanDec decoder (clk,cipher,plain,ok,val);
68/*
69    reg        ci;
70    reg [7:0]  ch;
71
72    initial begin
73        ci = 0;
74        ch = 0;
75    end
76
77    always @ (posedge clk) begin
78        ci = cipher;
79        ch = character;
80    end
81
82*/
83endmodule // main
84
85
86module huffmanEnc (clk, addr, cipher, character,ok,val);
87    input        clk;
88    input [4:0]  addr;
89    input        ok;
90    output       val;
91    output       cipher;
92    output [7:0] character;
93
94    reg [7:0]    character;
95    reg [9:0] shiftreg;
96    reg [2:0] count;
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 [2:0] cpts;
154        begin: _cpt
155            if (cpts>=5)
156              cpt=1;
157            else
158              cpt=0;
159        end
160    endfunction //val       
161
162    initial 
163        begin
164                character = ROM(addr);
165                shiftreg = code(character);
166        count=0;
167    end
168
169    always @ (posedge clk) begin 
170                if(count < 5 )
171                        if (shiftreg[9:1] <= 1 )
172                        begin
173                                count=count+1;
174                                character = ROM(addr);
175                                shiftreg = code(character); // load a new code
176                        end 
177                        else
178                        begin
179                                shiftreg = {1'b0, shiftreg[9:1]}; // shift right
180                        end
181           else
182                        if (ok==1) 
183                        begin
184                                count = 0;   
185                                character = ROM(addr);
186                                shiftreg = code(character);
187                        end 
188                        else 
189                        begin
190                                count=count;
191                        end 
192        //              else if((shiftreg == 1) || (shiftreg == 0)) begin
193        //                      count = 5;
194     //  end else begin
195        //    shiftreg = {1'b0, shiftreg[9:1]}; // shift right
196     //  end
197    end
198    assign val=cpt(count);
199    assign cipher = shiftreg[0];
200
201endmodule // huffmanEnc
202
203
204// The output plain is 0 except for one clock cycle when a character has
205// been decoded.
206module huffmanDec (clk,cipher,plain,ok,val);
207    input        clk;
208    input        cipher;
209    input        val;
210    output       ok;
211    output [7:0] plain;
212
213    reg [9:0]    state;
214    //reg          ok;
215    wire             leaf;
216    wire [7:0]   character;
217
218    initial state = 0;
219    //initial ok = 0;
220
221    // This function maps states to characters.  All non-leaf states are
222    // mapped to NUL.  The leaf states are mapped to the ASCII code of the
223    // corresponding symbol.
224    function [7:0] map;
225        input [9:0] state;
226        begin: _map
227            case (state)
228                9: map = 69; // E
229               13: map = 32; // space
230               17: map = 83; // S
231               22: map = 65; // A
232               23: map = 73; // I
233               24: map = 79; // O
234               25: map = 82; // R
235               26: map = 78; // N
236           30: map = 84; // T
237               31: map = 85; // U
238               32: map = 80; // P
239               33: map = 70; // F
240               34: map = 67; // C
241               38: map = 76; // L
242               43: map = 72; // H
243               59: map = 68; // D
244               76: map = 87; // W
245               89: map = 71; // G
246               90: map = 89; // Y
247              122: map = 77; // M
248              243: map = 66; // B
249              244: map = 86; // V
250              303: map = 81; // Q
251              305: map = 75; // K
252              306: map = 88; // X
253              609: map = 90; // Z
254              610: map = 74; // J
255              default: map = 0;
256            endcase // case(state)
257        end // block: _map
258    endfunction // map
259
260    assign plain = map(state);
261    assign leaf = plain != 0;
262    assign ok = val;
263    always @ (posedge clk) begin
264                state = (val ? 0 : ((leaf ? 0 : {state[8:0],1'b0}) + (cipher ? 2 : 1)));
265                //ok = val;
266    end
267
268endmodule // huffmanDec
Note: See TracBrowser for help on using the repository browser.