source: caseStudy_Huffmann/huffmann/huff_original/huff.v

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

Hufmann case study

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