3 * Copyright 2002,2006 Free Software Foundation, Inc.
5 * This file is part of GNU Radio
7 * GNU Radio is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 3, or (at your option)
12 * GNU Radio is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Radio; see the file COPYING. If not, write to
19 * the Free Software Foundation, Inc., 51 Franklin Street,
20 * Boston, MA 02110-1301, USA.
29 * Trellis-encode a whole pile of 12 data segments for ATSC.
30 * This also includes scrambling the data among twelve Trellis encoders.
32 * Input is twelve 207-byte blocks of raw data (Reed-Solomon output that's
33 * been scrambled up by interleaving with other blocks).
35 * Output is 12 x 208 x 4 bytes, each byte containing a 3-bit symbol.
36 * The first 4 bytes are the segment sync symbol.
38 Got the first version of Trellis encoder coded. Compiles, but I
39 didn't realize that each data segment contains an odd number of BITS!
40 The second data segment in a field starts by pulling bits out of the
41 middles of the bytes it's encoding. You actually have to read all the
42 entries in that table on page 59 AND 60 to get it.
44 There's a 4-segment asymmetric pattern of bit accesses.
45 There's a 3-segment asymmetric pattern of muxing encoders.
47 The result is there's a 12-segment pattern that repeats throughout
48 the encoding of a field. So this routine now encodes 12 segments at once.
50 This encoding system was either designed by a complete idiot or by
51 a complete genius. It's highly complex when it could have been very
52 simple. Now the question is whether
53 this incredible complexity buys us anything subtle and important.
56 #define SEGMENT_SIZE 207
57 #define INPUT_SIZE (SEGMENT_SIZE * 12)
58 #define DIBITS_PER_BYTE 4
59 #define EXTRAS (4 * 12) /* FIXME, sync symbols and such */
60 #define SYMBOLS_OUT ((INPUT_SIZE * DIBITS_PER_BYTE) + EXTRAS)
61 #define SEGOF(x) ( (x) / ((SEGMENT_SIZE+1) * DIBITS_PER_BYTE))
62 #define SYMOF(x) (((x) % ((SEGMENT_SIZE+1) * DIBITS_PER_BYTE))-4)
64 #define ENCODER_SEG_BUMP 4
67 /* Shift counts to bit numbers (high order, low order); 9x entries unused */
68 static const int bit1[8] = {1, 99, 3, 98, 5, 97, 7, 96};
69 static const int bit2[8] = {0, 99, 2, 98, 4, 97, 6, 96};
71 /* Detailed Debugging */
75 * Build indirect data structures to say which symbols go into which
76 * encoder, and then where the resulting dibits from the encoders go.
79 build_decode_structures (char *fileout)
84 int trellis_wheredata[ENCODERS];
85 unsigned char *symp, *next_sym_seg;
86 unsigned char symbols[SYMBOLS_OUT];
89 int skip_encoder_bump;
90 int *enco_syms[ENCODERS];
91 int *enco_dibits[ENCODERS];
93 /* The data structures we'll build and then spit out... */
94 int sync_symbol_indices[1000];
95 int sync_symbol_indices_max;
96 int enco_which_syms[ENCODERS][INPUT_SIZE];
97 int enco_which_dibits[ENCODERS][INPUT_SIZE];
99 #define BIT_PTR(int,shif) (((int) << 3) | ((shif) & 0x7))
100 /* Running indices into them as we build 'em... */
101 int *syncsyms = sync_symbol_indices;
103 /* Start our running pointers at the start of our per-encoder subarrays */
104 for (i = 0; i < ENCODERS; i++) {
105 enco_dibits[i] = enco_which_dibits[i];
106 enco_syms[i] = enco_which_syms[i];
109 encoder = ENCODERS - ENCODER_SEG_BUMP;
110 skip_encoder_bump = 0;
117 /* Associate data bytes with the Trellis encoders.
118 They get loaded or stored in an order that depends on where we are in the
119 segment sync progress (sigh).
120 GRR! When the chunk reload happens at the same time as the
121 segment boundary, we should bump the encoder NOW for the reload,
122 rather than LATER during the bitshift transition!!! */
123 if (symp >= next_sym_seg) {
124 encoder = (encoder + ENCODER_SEG_BUMP) % ENCODERS;
125 skip_encoder_bump = 1;
128 /* Remember where the data bytes are going to go, once we've
129 accumulated them from the 12 interleaved decoders */
130 for (i = 0; i < ENCODERS; i++) {
131 trellis_wheredata[encoder] = chunk+i;
133 if (encoder >= ENCODERS) encoder = 0;
136 for (shift = 6; shift >= 0; shift -= 2) {
138 /* Segment boundaries happen to occur on some bitshift transitions. */
139 if (symp >= next_sym_seg) {
140 /* Segment transition. Output a data segment sync symbol, and
141 mess with the trellis encoder mux. */
142 *syncsyms++ = symp - symbols;
144 next_sym_seg = symp + (SEGMENT_SIZE * DIBITS_PER_BYTE);
146 if (!skip_encoder_bump)
147 encoder = (encoder + ENCODER_SEG_BUMP) % ENCODERS;
148 skip_encoder_bump = 0;
151 /* Now run each of the 12 Trellis encoders to spit out 12 symbols.
152 Each encoder takes input from the same byte of the chunk, but the
153 outputs of the encoders come out in various orders.
154 NOPE -- this is false. The encoders take input from various
155 bytes of the chunk (which changes at segment sync time), AND
156 they also come out in various orders. You really do have to
157 keep separate track of: the datasegs bytes, the encoders, and
158 the symbol bytes -- because they're all moving with respect to
160 for (i = 0; i < ENCODERS; i++) {
162 printf ("Seg %ld Symb %3ld Trell %2d Byte %6d Bits %d-%d = ",
163 (long) SEGOF(symp-symbols), (long) SYMOF(symp-symbols),
164 encoder, trellis_wheredata[encoder],
165 bit1[shift], bit2[shift]);
167 /* Decoding: Grab symbol, run through decoder, slice dibit into
169 /* This symbol goes into this encoder next */
170 *(enco_syms[encoder]++) = symp - symbols;
172 /* The next output from this encoder goes into these dibits */
173 *(enco_dibits[encoder]++) = BIT_PTR(trellis_wheredata[encoder], shift);
175 encoder++; if (encoder >= ENCODERS) encoder = 0;
180 /* Now dump out the chunk of 12 data bytes that the twelve decoders have
182 unsigned char trellis_buffer[ENCODERS];
184 unsigned char symbol;
186 for (i = 0; i < ENCODERS; i++) {
187 datasegs [trellis_wheredata[encoder]] = trellis_buffer[encoder];
189 if (encoder >= ENCODERS) encoder = 0;
190 } /* Dumping encoder bytes */
194 /* Now print the resulting data structures in C++ */
196 if (!freopen(fileout, "w", stdout))
200 * atsc_viterbi_mux.cc\n\
202 * Data structures for knowing which symbols are fed to which\n\
203 * Viterbi decoders, and then where to put the resulting output dibits.\n\
205 * Generated by 'atsc_viterbi_gen.cc'.\n\
207 sync_symbol_indices_max = syncsyms - sync_symbol_indices;
208 printf ("const unsigned int sync_symbol_indices_max = %d;\n",
209 sync_symbol_indices_max);
210 printf ("const unsigned int sync_symbol_indices[%d] = {\n ",
211 sync_symbol_indices_max);
212 for (i = 0; i < sync_symbol_indices_max; i++) {
213 printf ("%d,%s", sync_symbol_indices[i], (7 == i%8)? "\n ": " ");
217 enco_which_max = enco_dibits[0] - enco_which_dibits[0];
218 for (i = 0; i < ENCODERS; i++)
219 if (enco_which_max != enco_dibits[i] - enco_which_dibits[i]) {
220 cerr << "Encoder " << i << " has different max_dibits " <<
221 enco_dibits[i] - enco_which_dibits[i] << " than " << enco_which_max;
225 printf ("const unsigned int enco_which_max = %d;\n" , enco_which_max);
227 printf ("const unsigned int enco_which_syms[%d][%d] = {\n",
228 ENCODERS, enco_which_max);
229 for (i = 0; i < ENCODERS; i++) {
230 printf (" /* %d */\n {", i);
231 for (j = 0; j < enco_which_max; j++)
232 printf ("%d,%s", enco_which_syms[i][j], (7 == j%8)? "\n ": " ");
237 printf ("const unsigned int enco_which_dibits[%d][%d] = {\n",
238 ENCODERS, enco_which_max);
239 for (i = 0; i < ENCODERS; i++) {
240 printf (" /* %d */\n {", i);
241 for (j = 0; j < enco_which_max; j++)
242 printf ("%d,%s", enco_which_dibits[i][j], (7 == j%8)? "\n ": " ");
252 cerr << "atsc_viterbi_gen: Usage:\n";
253 cerr << " ./atsc_viterbi_gen -o atsc_viterbi_mux.cc\n";
254 cerr << "That's all, folks!\n";
260 main(int argc, char **argv)
262 if (argc != 3) return usage();
263 if (argv[1][0] != '-'
265 || argv[1][2] != 0 ) return usage();
266 return build_decode_structures(argv[2]);