𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

Code Design for Dependable Systems: Theory and Practical Applications

✍ Scribed by Eiji Fujiwara


Publisher
Wiley-Interscience
Year
2006
Tongue
English
Leaves
718
Edition
1
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


Theoretical and practical tools to master matrix code design strategy and techniqueError correcting and detecting codes are essential to improving system reliability and have popularly been applied to computer systems and communication systems. Coding theory has been studied mainly using the code generator polynomials; hence, the codes are sometimes called polynomial codes. On the other hand, the codes designed by parity check matrices are referred to in this book as matrix codes. This timely book focuses on the design theory for matrix codes and their practical applications for the improvement of system reliability. As the author effectively demonstrates, matrix codes are far more flexible than polynomial codes, as they are capable of expressing various types of code functions.In contrast to other coding theory publications, this one does not burden its readers with unnecessary polynomial algebra, but rather focuses on the essentials needed to understand and take full advantage of matrix code constructions and designs. Readers are presented with a full array of theoretical and practical tools to master the fine points of matrix code design strategy and technique: Code designs are presented in relation to practical applications, such as high-speed semiconductor memories, mass memories of disks and tapes, logic circuits and systems, data entry systems, and distributed storage systems New classes of matrix codes, such as error locating codes, spotty byte error control codes, and unequal error control codes, are introduced along with their applications* A new parallel decoding algorithm of the burst error control codes is demonstratedIn addition to the treatment of matrix codes, the author provides readers with a general overview of the latest developments and advances in the field of code design. Examples, figures, and exercises are fully provided in each chapter to illustrate concepts and engage the reader in designing actual code and solving real problems. The matrix codes presented with practical parameter settings will be very useful for practicing engineers and researchers. References lead to additional material so readers can explore advanced topics in depth.Engineers, researchers, and designers involved in dependable system design and code design research will find the unique focus and perspective of this practical guide and reference helpful in finding solutions to many key industry problems. It also can serve as a coursebook for graduate and advanced undergraduate students.

✦ Table of Contents


Code Design for Dependable Systems, Theory and Practical Applications......Page 1
Contents......Page 7
Preface......Page 11
Origin of Faults......Page 19
Nature of Faults......Page 20
1.2 ERROR MODELS......Page 22
1.2.2 Random Errors, Clustered Errors, and Their Mified-Type Errors......Page 23
1.2.3 Symmetric Errors, Asymmetric Errors, and Unidirectional Errors......Page 25
Prediction & Comparison......Page 26
1.3.2 Error Recovery / Error Masking......Page 27
Retry......Page 28
N-Modular Redundancy (NMR) and Recon.guration......Page 29
1.4 CODE DESIGN PROCESS FOR DEPENDABLE SYSTEMS......Page 32
1.4.1 Code Functions......Page 33
1.4.2 Code Deisgn Process......Page 34
2.1.1 Groups and Rings......Page 39
Subgroups......Page 40
Rings......Page 41
2.1.2 Ffields......Page 42
Polynomial Representation......Page 44
Matrix Representation......Page 46
2.1.4 Properties of Galois Ffield GF(2^m)......Page 47
Minimal Polynomial......Page 48
2.2 LINEAR CODES......Page 49
Linear Dependence / Independence......Page 50
2.2.2 Linear Codes as Vector Spaces......Page 51
2.2.3 Matrix Algebra......Page 52
Echelon Canonical Form......Page 53
Nonsingular Matrix......Page 54
2.2.4 Distance and Error Control Capability......Page 55
Error Correction and Detection......Page 56
2.2.5 Parity-Check Matrices for Linear Codes......Page 57
Parity-Check Matrix......Page 58
Syndrome Decoding for Standard Array......Page 61
2.3.1 Simple Parity-Check Codes......Page 64
2.3.2 Hamming Single Error Correcting (SEC) Codes......Page 65
2.3.3 Hamming Single Error Correcting and Double Error Detecting (SEC-DED) Codes......Page 68
Algebraic Structure of Cyclic Codes......Page 69
2.3.5 Binary BCH Codes......Page 74
Decoding BCH Codes......Page 77
2.3.6 Reed-Solomon Codes as Nonbinary BCH Codes......Page 81
Determination of Error Values......Page 82
Burst Errors......Page 84
Other Single-Burst Error Correcting Codes......Page 85
Interleaving......Page 87
3 Code Design Techniques for Matrix Codes......Page 93
3.1.2 Lowest Density MDS Codes......Page 94
Set of Matrices Satisfying (P1), (P2), and (P3)......Page 95
Set of Matrices Satisfying (P1), (P2), and (P3')......Page 96
Lowest Density Bounds on MDS Codes......Page 97
3.2 ODD-WEIGHT-COLUMN CODES......Page 98
3.3 EVEN-WEIGHT-ROW CODES......Page 100
3.4 ODD-WEIGHT-ROW CODES......Page 102
3.5.1 Code Concept......Page 103
3.5.2 Maximum Code Length of Rotational Codes......Page 105
4 Codes for High-Speed Memories I: Bit Error Control Codes......Page 113
4.1.1 Odd-Weight-Column Codes β€” Hsiao Codes β€”......Page 114
4.1.2 Davydov-Tombak Codes......Page 117
Shortening Algorithm......Page 119
4.1.3 Double-Bit Error Correction Using SEC-DED Codes......Page 120
4.2 MODIFIED DOUBLE-BIT ERROR CORRECTING BCH CODES......Page 121
Imai-Kamiyanagi Code......Page 123
4.2.2 Algebraic Parallel Decoding DEC-BCH Codes......Page 125
4.3 ON-CHIP ECCs......Page 126
4.3.1 Two-Dimensional Cross-Parity Codes for Soft Error Problems......Page 128
4.3.2 On-Chip Hamming SEC Codes for Yfield Improvement......Page 135
Augmented Product Code (APC)......Page 137
Combination of ECC and Spare Bit-Lines / Word-Lines......Page 138
5 Codes for High-Speed Memories II: Byte Error Control Codes......Page 149
5.1.1 Hamming-Type Codes......Page 150
5.1.2 Burton Code and Its Generalified 2-Redundant Codes......Page 155
5.1.3 Odd-Weight-Column Codes β€” Fujiwara Codes β€”......Page 159
Rotational Fujiwara Codes......Page 163
5.1.4 Maximal Codes β€” Hong-Patel Codes β€”......Page 165
5.2 SINGLE-BYTE ERROR CORRECTING AND DOUBLE-BYTE ERROR DETECTING (SbEC-DbED) CODES......Page 170
5.2.1 Reed-Solomon (RS) Codes......Page 172
5.2.2 Kaneda-Fujiwara Codes......Page 173
Rotational / Modularified SbEC-DbED Codes......Page 176
5.2.3 Chen Codes......Page 182
Converted Chen Codes......Page 185
5.3.1 Code Conditions and Bounds......Page 187
1. Design Method I......Page 188
2. Design Method II......Page 190
Algorithm for Finding Block Elements......Page 191
Lengthened Code......Page 194
5.3.3 Evaluation......Page 195
6 Codes for High-Speed Memories III: Bit / Byte Error Control Codes......Page 203
6.1.1 Burst Error Detecting SEC-DED Codes (SEC-DED-BED Codes)......Page 204
6.1.2 Generalified Burst Error Detecting SEC-DED Codes......Page 213
Rotational Burst Error Detecting SEC-DED Codes......Page 218
Construction 1......Page 221
Construction 2......Page 222
Codes for R = b +......Page 226
6.2.1 Subfield......Page 233
Design by Using Elements of Subfield......Page 235
Design by Using Elements of Multiplicative Coset......Page 237
Design by Using Elements of Additive Coset......Page 238
)......Page 243
6.3 SINGLE-BYTE ERROR CORRECTING AND DOUBLE-BIT ERROR CORRECTING (SbEC-DEC) CODES......Page 246
Code Conditions and Bounds......Page 247
Code Design Method......Page 248
Evaluation......Page 249
Code Design Method......Page 250
Decoding Procedure......Page 252
6.3.3 SbEC-(DEC)B Codes......Page 254
Code Conditions and Bounds......Page 255
Code Design Method......Page 257
Evaluation......Page 258
6.4 SINGLE-BYTE ERROR CORRECTING AND SINGLE-BYTE PLUS SINGLE-BIT ERROR DETECTING (SbEC-(Sb ΓΎ S)ED) CODES......Page 260
6.4.1 Code Conditions and Bounds......Page 261
Design Method I......Page 263
Design Method II......Page 265
6.4.3 Evaluation......Page 267
7 Codes for High-Speed Memories IV: Spotty Byte Error Control Codes......Page 279
7.2 SINGLE SPOTTY BYTE ERROR CORRECTING (St =bEC) CODES......Page 280
7.2.1 Codes Based on Tensor Product of Matrices......Page 281
7.2.2 Efficient St=bEC Codes......Page 282
7.2.3 Practical Examples......Page 286
7.3 SINGLE SPOTTY BYTE ERROR CORRECTING AND SINGLE-BYTE ERROR DETECTING Γ°St=bEC-SbED) CODES......Page 290
7.3.1 Decoding St=b EC-SbED Codes......Page 292
7.3.2 Perfect St=bEC-SbED Code with t ΒΌ b –1......Page 294
7.3.3 St=BEC-SbEC-SBED Codes......Page 297
7.4.2 Design for St=bEC-Dt=bED Codes and St=bEC-Dt=bED-SbED Codes......Page 300
Evaluation......Page 302
Preliminaries......Page 306
Code Design......Page 308
Decoding......Page 312
Examples and Evaluation......Page 314
7.5.2 A General Class of Codes for m-Spotty Byte Errors......Page 317
Preliminaries......Page 318
Code Design......Page 319
Decoding......Page 322
Evaluation......Page 323
Code Conditions and Bounds......Page 324
Code Design......Page 325
Decoding......Page 327
Code Conditions and Bounds......Page 328
Code Design......Page 330
Decoding......Page 331
Evaluation......Page 332
Preliminaries......Page 335
Code Design......Page 337
Decoding......Page 339
Evaluation......Page 342
8 Parallel Decoding Burst / Byte Error Control Codes......Page 351
8.1 PARALLEL DECODING BURST ERROR CONTROL CODES 8.1.1 Error Pattern Generation by Inverse Matrices......Page 352
8.1.2 Frames for Burst Error Location......Page 354
Algorithm 8.1......Page 357
8.1.3 Parallel Decoding Circuit......Page 359
and B......Page 360
Algorithm 8.2 for Optimal H......Page 361
Circuit Gate Amount and Check-Bit Length......Page 362
Parallel Decoding Byte Error Control Codes......Page 365
8.1.5 Multiple Burst / Byte Error Correction......Page 366
8.2.1 Preliminaries......Page 367
8.2.2 Parallel Decoding......Page 368
8.3 TRANSIENT BEHAVIOR OF PARALLEL ENCODING / DECODING CIRCUITS OF ERROR CONTROL CODES......Page 369
8.3.1 Introduction......Page 370
Glitch Generation......Page 371
Glitch Accumulation......Page 372
Exhaustive Examinations of Transient Behavior......Page 374
Estimating the Transient Behavior......Page 378
Importance of Weight in H Matrix Design......Page 380
8.3.4 Two Potential Solutions to Reduce Glitch Accumulation......Page 381
8.3.5 Maximum Temporal Accumulated Glitches (TAGs) and Matrix Code Design......Page 383
9.1 ERROR LOCATION OF FAULTY PACKAGES AND FAULTY CHIPS......Page 389
9.2 BLOCK ERROR LOCATING (Sb=p bEL) CODES......Page 392
Necessary and Sufficient Conditions......Page 393
Bounds......Page 394
1. Codes Designed by Tensor Product β€” Codes I β€”......Page 395
Codes II β€”......Page 396
Design of the Parity-Check Matrices......Page 397
Expanding the Code Length......Page 401
9.3.3 Decoding Procedure......Page 402
Error Detection Capabilities......Page 403
Decoder Hardware Complexity......Page 404
9.4.1 Code Conditions and Bounds......Page 405
9.4.2 Design for SEC-Se=bEL Codes......Page 408
Code Length......Page 409
9.5.1 Frame Set......Page 412
9.5.2 Burst Error Locating (Bl EL) Codes......Page 413
9.5.3 Single-Bit Error Correcting and Burst Error Locating (SEC-Bl EL) Codes......Page 414
9.5.5 Evaluation......Page 418
9.6.1 Preliminaries......Page 420
EC Codes......Page 421
EL Codes......Page 422
Conditions for Codes with Combination of Code Functions......Page 423
9.6.3 Relation between Error Locating Codes and Error Correcting / Detecting Codes......Page 424
10.1 ERROR MODELS FOR UEC CODES AND UEP CODES......Page 429
Code Conditions and Bounds......Page 433
SEC Codes......Page 435
Evaluation......Page 436
Code Conditions and Bounds......Page 438
Design for Optimal FbEC SEC-DED Codes......Page 440
Evaluation......Page 442
Code Conditions and Bounds......Page 443
Code Design II......Page 444
Evaluation......Page 446
10.3.2 Burst Error Control UEP Codes β€” (Bl EC)no -(SEC)n1 UEP Codes β€”......Page 447
Code Conditions and Bounds......Page 448
UEP Code......Page 450
Decoding Procedure......Page 453
Evaluation......Page 454
10.4.1 Application of q-Ary UEC Codes to Holographic Memories......Page 455
1. Combination of Error Control Coding and Block Modulation Coding for......Page 456
2. q-Ary FlEC | SEC Codes......Page 457
3. q-Ary (Fl+S)EC Codes......Page 460
4. Evaluation......Page 464
Comparison of Error Correction Capabilities......Page 465
LZW Coding......Page 466
LZ77 Coding......Page 467
(1) UEP in LZW Coding......Page 469
(2) UEP in LZ77 Coding......Page 470
11.1 TAPE MEMORY CODES......Page 481
11.1.1 Optimal Rectangular Codes (ORC)......Page 482
11.1.2 Adaptive Cross-Parity (AXP) Codes......Page 491
11.1.3 Interleaved RS SbEC Codes for Mass Storage System (MSS)......Page 497
11.2 MAGNETIC DISK MEMORY CODES......Page 503
11.2.1 Fire Codes......Page 504
Distance-4 RS Code Interleaved to Degree 3......Page 508
Two-Level Coding for Multiple-Burst Errors......Page 511
11.2.4 Introduction to Disk Array Codes......Page 513
11.3.1 Cross-interleaved RS Code (CIRC)......Page 516
Codes for Compact Disc (CD) Digital Audio Systems......Page 519
Codes for Digital Data Storage (CD-ROM)......Page 520
11.3.2 Long-Distance Code (LDC)......Page 521
11.3.3 RS Product Codes for DVDs......Page 523
12 Coding for Logic and System Design......Page 533
12.1.1 General Concept......Page 534
1. Fault Secure and Self-testing......Page 536
2. Error Secure and Error Preserving......Page 541
3. Self-checking Logic Networks......Page 543
12.1.2 Checker Concept......Page 547
12.2.1 Parity Code Checker......Page 552
12.2.2 Two-Rail Code Checker......Page 554
12.2.3 Generalified Prediction Checker (GPC)......Page 558
Checker Implementation......Page 559
Self-testing GPC......Page 565
Applications to Built-in Testing......Page 567
12.3.1 Parity-Checked Adder......Page 568
12.3.2 Addition with Checksum Codes......Page 576
12.3.3 ALU with Parity-Based Codes......Page 578
12.4 SELF-CHECKING DESIGN FOR COMPUTER SYSTEMS......Page 586
Electronic Switching Systems......Page 587
2. (4, 2) Concept Machine......Page 588
(2) RAS Design for Recent General Purpose System and Server Machine......Page 590
DEC-TED BCH Codes......Page 591
1. Duplicate VLSI Processors......Page 594
2. Self-checking Microprocessors......Page 595
3. On-Chip ECCs in Recent Microprocessors......Page 599
13.1 M-ARY ASYMMETRIC ERRORS IN DATA ENTRY SYSTEMS......Page 615
13.2.1 Systematic Codes......Page 616
-Asymmetric Symbol Error......Page 617
Bound for Single -Asymmetric Symbol Error Correcting Codes......Page 619
Rings......Page 620
Parity-Check Matrix H over Rings......Page 622
Mapping Functions......Page 623
Code Design......Page 625
3. Decoding Procedure......Page 627
4. Evaluation......Page 629
Rooted Tree T(q......Page 630
2. Code Design......Page 631
(1) Set-Partitioning Algorithm......Page 632
New Set-Partitioning Algorithm......Page 633
(2) Code Design......Page 634
3. Decoding Procedure......Page 637
4. Evaluation......Page 638
13.3 NONSYSTEMATIC M-ARY ASYMMETRIC ERROR CORRECTING CODES WITH DELETION / INSERTION / ADJACENT-SYMBOLTRANSPOSITION ERROR CORREC......Page 639
13.3.1 Preliminaries......Page 640
13.3.2 Code Design......Page 641
1. Code Design......Page 644
2. Decoding Procedure......Page 645
3. Evaluation......Page 647
13.4.1 QR Codes......Page 648
Formation of the QR Code......Page 649
Check Information Generationβ€”Encodingβ€”......Page 650
Decoding QR Codes......Page 652
1. One-dimensional Unidirectional Burst Error Correcting Codes......Page 653
(1) Codeword Structure......Page 654
(2) Code Design......Page 655
(3) Decoding Procedure......Page 657
(4) Evaluation......Page 659
14 Codes for Multiple / Distributed Storage Systems......Page 665
1. MDS Array Codes with Code Length n p......Page 666
2. Modified MDS Array Codes with Code Length n = p + r......Page 669
Encoding Procedure......Page 671
Decoding Two Erasures......Page 672
Algebraic Description of EVENODD......Page 673
Encoding Procedure......Page 674
Decoding Procedure......Page 676
System Models......Page 677
14.2.1 Models of Distributed Storage Systems and Code Conditions......Page 678
Code Conditions for Direct Decoding for t Erased Disk Data......Page 679
14.2.2 BIBD Codes......Page 680
14.2.3 Additive Codes......Page 684
14.2.4 Extended BIBD Codes and Additive Codes......Page 686
Extended BIBD Codes......Page 687
Extended Additive-3 Codes......Page 688
Evaluation......Page 690
Index......Page 695


πŸ“œ SIMILAR VOLUMES


Code Design for Dependable Systems: Theo
✍ Eiji Fujiwara πŸ“‚ Library πŸ“… 2006 πŸ› Wiley-Interscience 🌐 English

Theoretical and practical tools to master matrix code design strategy and technique Error correcting and detecting codes are essential to improving system reliability and have popularly been applied to computer systems and communication systems. Coding theory has been studied mainly us

Nonrecursive Control Design for Nonlinea
✍ Chuanlin Zhang, Jun Yang πŸ“‚ Library πŸ“… 2023 πŸ› CRC Press 🌐 English

<p><span>Based on the authors’ recent advances, this book focuses on a class of nonlinear systems with mismatched uncertainties/disturbances and discusses their typical control problems. It aims to provide a comprehensive view of the nonrecursive control theory and application guidelines.<br><br>Var

Mathematical theory of reliability of ti
✍ Igor N. Kovalenko, Nickolaj Yu. Kuznetzov, Philip A. Pegg πŸ“‚ Library πŸ“… 1997 πŸ› Wiley 🌐 English

One of the greatest problems in engineering is reliability. The performance of all machinery degrades over time and unless counteraction is taken at some point, any system will eventually fail. Once a system fails there are a number of possible solutions; the mathematical and statistical measurement