Preface |
|
viii | |
1 Introduction |
|
1 | (5) |
2 Definitions, Concepts, and Fundamental Characteristics of LDPC Codes |
|
6 | (10) |
|
2.1 Matrices and Matrix Dispersions of Finite Field Elements |
|
|
6 | (2) |
|
2.2 Fundamental Structural Properties and Performance Characteristics of LDPC Codes |
|
|
8 | (6) |
|
2.3 Discussion and Remarks |
|
|
14 | (2) |
3 A Review of PTG-Based Construction of LDPC Codes |
|
16 | (5) |
|
3.1 PTG-LDPC Code Construction |
|
|
16 | (4) |
|
3.2 Conclusion and Remarks |
|
|
20 | (1) |
4 An Algebraic Method for Constructing QC-PTG-LDPC Codes and Code Ensembles |
|
21 | (20) |
|
4.1 Construction of QC-PTG-LDPC Codes by Decomposing Base Matrices |
|
|
21 | (5) |
|
4.2 Construction of RC-Constrained PTG Parity-Check Matrices |
|
|
26 | (2) |
|
|
28 | (10) |
|
4.4 Construction of the Ensemble of PTG-LDPC Codes from an Algebraic Point of View |
|
|
38 | (2) |
|
4.5 Discussion and Remarks |
|
|
40 | (1) |
5 Superposition Construction of LDPC Codes |
|
41 | (10) |
|
5.1 SP-Construction of LDPC Codes and Its Graphical Interpretation |
|
|
41 | (2) |
|
5.2 Ensembles of SP-LDPC Codes |
|
|
43 | (1) |
|
5.3 Constraints on the Construction of SP-LDPC Codes Free of Cycles of Length |
|
|
44 | (4) |
|
5.4 SP-Construction of QC-LDPC Codes |
|
|
48 | (1) |
|
5.5 SP-Base Matrices over Nonnegative Integers |
|
|
49 | (1) |
|
5.6 Discussion and Remarks |
|
|
50 | (1) |
6 Construction of Base Matrices and RC-Constrained Replacement Sets for SP-Construction |
|
51 | (21) |
|
6.1 RC-Constrained Base Matrices |
|
|
51 | (2) |
|
6.2 Construction of RC-Constrained Replacement Sets Based on Hamming Codes |
|
|
53 | (6) |
|
6.3 Construction of RC-Constrained Replacement Sets Based on m-dimensional Euclidean Geometry EG(m, 2) over GF(2) |
|
|
59 | (3) |
|
6.4 Construction of RC-Constrained Replacement Sets Based on RC-Constrained Arrays of CPMs |
|
|
62 | (7) |
|
6.5 Discussion and Remarks |
|
|
69 | (3) |
7 SP-Construction of QC-LDPC Codes Using Matrix Dispersion and Masking |
|
72 | (26) |
|
7.1 A Deterministic SP-Construction of QC-LDPC Codes |
|
|
72 | (1) |
|
7.2 Conditions on Girth of CPM-QC-SP-LDPC Codes |
|
|
73 | (1) |
|
7.3 A Finite Field Construction of 2 x 2 SM-Constrained SP-Base Matrices and Their Associated CPM-QC-SP-LDPC Codes |
|
|
74 | (3) |
|
|
77 | (7) |
|
7.5 Design of Masking Matrices |
|
|
84 | (8) |
|
7.6 Construction of CPM-QC-SP-LDPC Codes for Correcting Bursts of Erasures by Masking |
|
|
92 | (3) |
|
7.7 Discussion and Remarks |
|
|
95 | (3) |
8 Doubly QC-LDPC Codes |
|
98 | (13) |
|
8.1 Base Matrices with Cyclic Structure |
|
|
98 | (2) |
|
8.2 CPM-D-SP-Construction of Doubly QC-LDPC Codes |
|
|
100 | (4) |
|
8.3 Masking and Variations |
|
|
104 | (4) |
|
8.4 SP-Construction of CPM-QC-SP-LDPC Codes |
|
|
108 | (1) |
|
8.5 Discussion and Remarks |
|
|
108 | (3) |
9 SP-Construction of Spatially Coupled QC-LDPC Codes |
|
111 | (27) |
|
9.1 Base Matrices and Their Structural Properties |
|
|
112 | (2) |
|
9.2 Type-1 QC-SC-LDPC Codes |
|
|
114 | (6) |
|
9.3 Type-2QC-SC-LDPC Codes |
|
|
120 | (3) |
|
9.4 Terminated and Tailbiting CPM-QC-SC-LDPC Codes |
|
|
123 | (6) |
|
9.5 A More General Construction of Type-1 CPM-QC-SC-LDPC Codes |
|
|
129 | (5) |
|
9.6 A More General Construction of Type-2 CPM-QC-SC-LDPC Codes |
|
|
134 | (1) |
|
9.7 Discussion and Remarks |
|
|
135 | (3) |
10 Globally Coupled QC-LDPC Codes |
|
138 | (28) |
|
10.1 Construction of CN-Based QC-GC-LDPC Codes: Method-1 |
|
|
138 | (8) |
|
10.2 A Local/Global Two-Phase Decoding of CN-Based CPM-QC-GC-LDPC Codes |
|
|
146 | (3) |
|
10.3 Construction of CN-Based GC-LDPC Codes: Method-2 |
|
|
149 | (5) |
|
10.4 CPM-Dispersion Construction of CN-Based Product QC-GC-LDPC Codes |
|
|
154 | (8) |
|
10.5 Discussion and Remarks |
|
|
162 | (4) |
11 SP-Construction of Nonbinary LDPC Codes |
|
166 | (43) |
|
11.1 General SP-Construction of NB LDPC Codes Using Binary Base Matrices |
|
|
166 | (1) |
|
11.2 SP-Construction of NB QC-LDPC Codes |
|
|
167 | (6) |
|
11.3 Construction of NB QC-SP-LDPC Codes Using q-ary CPM-Dispersion |
|
|
173 | (2) |
|
11.4 CPM-D Construction of NB CPM-QC-SP-LDPC Codes Using Binary-to-Nonbinary Replacement |
|
|
175 | (7) |
|
11.5 Algebraic Construction of NB QC-PTG-LDPC Codes |
|
|
182 | (11) |
|
11.6 Construction of NB LDPC Codes from Reed—Solomon Codes |
|
|
193 | (4) |
|
11.7 Construction of NB QC-SP-LDPC Codes based on RS Codes |
|
|
197 | (8) |
|
11.8 Discussion and Remarks |
|
|
205 | (4) |
12 Conclusion and Remarks |
|
209 | (6) |
Appendices |
|
215 | (22) |
|
A RC-Constrained Arrays of CPMs Constructed Based on Partial Geometries |
|
|
217 | (8) |
|
A.1 RC-Constrained Arrays of CPMs Constructed Based on Two-Dimensional Euclidean Geometries over Finite Fields |
|
|
218 | (5) |
|
A.2 RC-Constrained Arrays of CPMs Based on Partial Geometries Constructed from Prime Fields |
|
|
223 | (2) |
|
B An Algorithm for Searching Compatible Masking and Base Matrices for the CPM-Dispersion Construction of QC-LDPC Codes |
|
|
225 | (3) |
|
C Iterative Decoding Algorithm for NB LDPC Codes |
|
|
228 | |
|
|
228 | (1) |
|
|
229 | (6) |
|
C.3 The NB LDPC Decoding Algorithm |
|
|
235 | (2) |
References |
|
237 | (7) |
Index |
|
244 | |
9781491937099 |
|
Preface |
|
xi | |
1 What Is Pig? |
|
1 | (12) |
|
Pig Latin, a Parallel Data Flow Language |
|
|
1 | (2) |
|
Comparing Query and Data Flow Languages |
|
|
2 | (1) |
|
|
3 | (5) |
|
MapReduce's "Hello World" |
|
|
5 | (1) |
|
How Pig Differs from MapReduce |
|
|
6 | (2) |
|
|
8 | (2) |
|
|
10 | (1) |
|
|
10 | (3) |
2 Installing and Running Pig |
|
13 | (18) |
|
Downloading and Installing Pig |
|
|
13 | (3) |
|
Downloading the Pig Package from Apache |
|
|
13 | (1) |
|
|
14 | (1) |
|
Downloading Pig Artifacts from Maven |
|
|
15 | (1) |
|
|
15 | (1) |
|
Downloading Pig from Distributions |
|
|
15 | (1) |
|
|
16 | (10) |
|
Running Pig Locally on Your Machine |
|
|
17 | (2) |
|
Running Pig on Your Hadoop Cluster |
|
|
19 | (2) |
|
|
21 | (2) |
|
Command-Line and Configuration Options |
|
|
23 | (2) |
|
|
25 | (1) |
|
|
26 | (2) |
|
Entering Pig Latin Scripts in Grunt |
|
|
26 | (1) |
|
|
27 | (1) |
|
Controlling Pig from Grunt |
|
|
28 | (1) |
|
Running External Commands |
|
|
29 | (1) |
|
|
29 | (2) |
3 Pig's Data Model |
|
31 | (14) |
|
|
31 | (5) |
|
|
31 | (3) |
|
|
34 | (2) |
|
|
36 | (1) |
|
|
36 | (9) |
|
|
39 | (6) |
4 Introduction to Pig Latin |
|
45 | (32) |
|
|
45 | (1) |
|
|
46 | (1) |
|
|
46 | (1) |
|
|
46 | (3) |
|
|
46 | (2) |
|
|
48 | (1) |
|
|
48 | (1) |
|
|
49 | (19) |
|
|
49 | (6) |
|
|
55 | (2) |
|
|
57 | (3) |
|
|
60 | (1) |
|
|
61 | (1) |
|
|
62 | (2) |
|
|
64 | (1) |
|
|
65 | (1) |
|
|
65 | (3) |
|
|
68 | (9) |
|
|
68 | (2) |
|
Registering UDFs in Scripting Languages |
|
|
70 | (1) |
|
|
71 | (1) |
|
Calling Static Java Functions |
|
|
72 | (1) |
|
|
73 | (4) |
5 Advanced Pig Latin |
|
77 | (36) |
|
Advanced Relational Operations |
|
|
77 | (21) |
|
Advanced Features of foreach |
|
|
77 | (5) |
|
Casting a Relation to a Scalar |
|
|
82 | (1) |
|
Using Different Join Implementations |
|
|
83 | (5) |
|
|
88 | (1) |
|
|
89 | (1) |
|
|
90 | (2) |
|
|
92 | (1) |
|
|
93 | (2) |
|
|
95 | (3) |
|
|
98 | (1) |
|
Integrating Pig with Executables and Native Jobs |
|
|
98 | (4) |
|
|
99 | (2) |
|
|
101 | (1) |
|
split and Nonlinear Data Flows |
|
|
102 | (4) |
|
|
106 | (2) |
|
|
106 | (1) |
|
|
107 | (1) |
|
|
108 | (5) |
|
|
108 | (1) |
|
|
109 | (2) |
|
Including Other Pig Latin Scripts |
|
|
111 | (2) |
6 Developing and Testing Pig Latin Scripts |
|
113 | (22) |
|
|
113 | (18) |
|
Syntax Highlighting and Checking |
|
|
113 | (1) |
|
|
114 | (1) |
|
|
115 | (7) |
|
|
122 | (1) |
|
|
123 | (2) |
|
|
125 | (4) |
|
|
129 | (2) |
|
Testing Your Scripts with PigUnit |
|
|
131 | (4) |
7 Making Pig Fly |
|
135 | (16) |
|
Writing Your Scripts to Perform Well |
|
|
136 | (4) |
|
|
136 | (1) |
|
|
137 | (1) |
|
Set Up Your Joins Properly |
|
|
138 | (1) |
|
Use Multiquery When Possible |
|
|
139 | (1) |
|
Choose the Right Data Type |
|
|
139 | (1) |
|
Select the Right Level of Parallelism |
|
|
139 | (1) |
|
Writing Your UDFs to Perform |
|
|
140 | (1) |
|
Tuning Pig and Hadoop for Your Job |
|
|
141 | (1) |
|
Using Compression in Intermediate Results |
|
|
142 | (1) |
|
|
143 | (1) |
|
|
144 | (1) |
|
|
145 | (1) |
|
Processing Small Jobs Locally |
|
|
146 | (1) |
|
|
147 | (2) |
|
Schema Tuple Optimization |
|
|
149 | (1) |
|
|
150 | (1) |
8 Embedding Pig |
|
151 | (14) |
|
Embedding Pig Latin in Scripting Languages |
|
|
151 | (7) |
|
|
152 | (2) |
|
|
154 | (2) |
|
|
156 | (1) |
|
|
157 | (1) |
|
|
158 | (7) |
|
|
158 | (3) |
|
|
161 | (4) |
9 Writing Evaluation and Filter Functions |
|
165 | (42) |
|
Writing an Evaluation Function in Java |
|
|
165 | (21) |
|
|
166 | (1) |
|
Evaluation Function Basics |
|
|
166 | (4) |
|
|
170 | (4) |
|
Error Handling and Progress Reporting |
|
|
174 | (2) |
|
Constructors and Passing Data from Frontend to Backend |
|
|
176 | (6) |
|
|
182 | (2) |
|
Variable-Length Input Schema |
|
|
184 | (1) |
|
Memory Issues in Eval Funcs |
|
|
184 | (1) |
|
|
185 | (1) |
|
Shipping JARs Automatically |
|
|
185 | (1) |
|
|
186 | (4) |
|
The Accumulator Interface |
|
|
190 | (2) |
|
|
192 | (1) |
|
Writing Evaluation Functions in Scripting Languages |
|
|
193 | (14) |
|
|
193 | (3) |
|
|
196 | (2) |
|
|
198 | (3) |
|
|
201 | (4) |
|
|
205 | (1) |
|
Comparing Scripting Language UDF Features |
|
|
206 | (1) |
10 Writing Load and Store Functions |
|
207 | (24) |
|
|
208 | (13) |
|
Frontend Planning Functions |
|
|
208 | (2) |
|
Passing Information from the Frontend to the Backend |
|
|
210 | (1) |
|
|
211 | (5) |
|
Additional Load Function Interfaces |
|
|
216 | (5) |
|
|
221 | (7) |
|
Store Function Frontend Planning |
|
|
221 | (2) |
|
Store Functions and UDFContext |
|
|
223 | (1) |
|
|
223 | (4) |
|
|
227 | (1) |
|
|
227 | (1) |
|
Shipping JARs Automatically |
|
|
228 | (1) |
|
|
228 | (3) |
11 Pig on Tez |
|
231 | (32) |
|
|
231 | (5) |
|
|
236 | (2) |
|
Potential Differences When Running on Tez |
|
|
238 | (12) |
|
|
239 | (1) |
|
|
240 | (2) |
|
|
242 | (8) |
|
|
250 | (13) |
|
|
251 | (1) |
|
|
252 | (2) |
|
Operators and Implementation |
|
|
254 | (6) |
|
|
260 | (3) |
12 Pig and Other Members of the Hadoop Community |
|
263 | (12) |
|
|
263 | (2) |
|
|
264 | (1) |
|
|
265 | (1) |
|
|
265 | (1) |
|
|
266 | (1) |
|
|
266 | (5) |
|
|
267 | (2) |
|
|
269 | (1) |
|
|
270 | (1) |
|
|
271 | (1) |
|
|
272 | (3) |
13 Use Cases and Programming Examples |
|
275 | (26) |
|
|
275 | (5) |
|
|
280 | (5) |
|
|
285 | (4) |
|
|
289 | (8) |
|
Apache Pig Use Cases at Yahoo! |
|
|
290 | (1) |
|
Large-Scale ETL with Apache Pig |
|
|
291 | (1) |
|
Features That Make Pig Attractive |
|
|
291 | (3) |
|
|
294 | (2) |
|
|
296 | (1) |
|
|
297 | (4) |
|
Compute Arrival Rate and Conversion Rate |
|
|
298 | (1) |
|
Compute Sessions Triggered by a Push |
|
|
299 | (2) |
A Built-in User Defined Functions and PiggyBank |
|
301 | (32) |
Index |
|
333 | |