Average Complexity Evaluation of an MLD Algorithm Using the Trellis Structure for a Linear Block Code

スポンサーリンク

概要

• 論文の詳細を見る

• This letter is concerned with the evaluation of the average computational complexity of the maximum likelihood decoding of a linear block code using its trellis diagram. Each section of the L-section minimal trellis diagram for a linear block code consists of parallel components which are structurally identical subgraphs without cross connection between them. A parallel component is also known to be decomposed into subgraphs, and a decoding algorithm by using the structure of the subgraphs of parallel components was proposed, and an upper bound on the worst case computational complexity was derived. In this letter, the average computational complexity of the decoding algorithm is evaluated by computer simulation. We evaluated the average numbers of additions and comparisons performed in the decoding algorithm for example codes, (64, 45) extended and permuted binary primitive BCH code, the third order Reed-Muller (64, 42) code and its (64, 40) subcode. It is shown that the average numbers are much smaller than those for the worst case, and hence the decoding algorithm is efficient when the number of sections, L, is small, say 4 or 8, for the example codes. Especially, for the (64, 45) extended binary primitive BCH code with L = 4, the average numbers of additions and comparisons in the decoding algorithm for finding the survivor's metric of each state after finding the smallest metric among parallel branches are about 1/50 and 17/100 of those in the conventional exhaustive search, respectively. The number of additions and comparisons by the conventional search for all the example codes is smallest when L is 4. As a result, the decoding algorithm with L = 4 gives the smallest number of operations among those decoding methods considered here.

• 社団法人電子情報通信学会の論文
• 1995-09-25

著者

• Fujiwara T

  Osaka University

• Fujiwara Toru

  Department Of Multimedia Engineering Graduate School Of Information Science And Technology Osaka Uni

• KASAMI Tadao

  Graduate School of Information Science, Nara Institute of Science and Technology

• Fujiwara Toru

  Faculty of Engineering Science, Osaka University

• Kasami Tadao

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Fujiwara Toru

  Faculty Of Engineering Science Osaka University

• Fujiwara T

  Department Of Multimedia Engineering Graduate School Of Information Science And Technology Osaka Uni

• Nagano Hidehisa

  Faculty of Engineering Science, Osaka University

• Nagano H

  Ntt Communication Sci. Lab. Atsugi‐shi Jpn

関連論文

• Formation of Tissue Masses on Floral Inflorescence in A. thaliana Plants That Accumulate Reduced Levels of MT2a mRNA
• Formation of Tissue Masses on Floral Inflorescence in A. thaliana Plants That Accumulate Reduced Levels of MT2a mRNA (Plant Nutrition)
• Composition of Seed Storage Proteins Changed by Glutathione Treatment of Soybeans(Biochemistry & Molecular Biology)
• Independent roles of glutathione and O-acetyl-L-serine in regulation of sulfur-responsive gene expression in Arabidopsis thaliana
• Quantitative estimation of the contribution of the phloem in cadmium transport to grains in rice plants (Oryza sativa L.)(Plant Nutrition)
• Arabidopsis SNRK2.3 protein kinase is involved in the regulation of sulfur-responsive gene expression and O-acetyl-L-serine accumulation under limited sulfur supply(Plant Nutrition)
• Differential Distribution of Proteins Expressed in Companion Cells in the Sieve Element-Companion Cell Complex of Rice Plants
• Detection of nifH Sequences in Sugarcane (Saccharum officinarum L.) and Pineapple (Ananas comosus [L.] Merr.) (Soil Biology)
• Isolation and Characterization of a Novel Arabidopsis thaliana Mutant That Requires a High Concentration of Boron
• Expression of a Single-Chain Antibody against GA_ in Vascular Tissues Induces Dwarf Phenotype for Rice Plants(Plant Nutrition)
• Identification of Several Rice Genes Regulated by Si Nutrition(Plant Nutrition)
• Cloning of the Phloem-Specific Small Heat-Shock Protein from Leaves of Rice Plants(Plant Nutrition)
• Upregulation of the Genes for Ferritin, RNase, and DnaJ in Leaves of Rice Plants in Response to Sulfur Deficiency(Plant Nutrition)
• Cadmium Concentrations in the Phloem Sap of Rice Plants (Oryza saliva L.) Treated with a Nutrient Solution Containing Cadmium (Environment)
• Regulation of Sulfur-Responsive Gene Expression by Exogenously Applied Cytokinins in Arabidopsis thaliana
• Unlinkable Delivery System for Interactive Dramas(Application)(Cryptography and Information Security)
• MAP and LogMAP Decoding Algorithms for Linear Block Codes Using a Code Structure(Special Section on Information Theory and Its Applications)
• A Recursive Maximum Likelihood Decoding Algorithm for Some Transitive Invariant Binary Block Codes
• Low Weight Subtrellises for Binary Linear Block Codes and Their Applications
• Error Performance of Multilevel Block Coded 8-PSK Modulations Using Unequal Error Protection Codes for the Rayleigh Fading Channel
• An Improved Union Bound on Block Error Probability for Closest Coset Decoding
• On Branch Labels of Parallel Components of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes
• On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes (Special Section on Information Theory and Its Applications)
• Structural Analysis of Minimum Weight Codewords of the Extended (32, 21, 6) and (64, 45, 8) BCH Codes Using Invariance Property(HISC2006)
• The structure of the set of minimum weight codewords of the extended (32,21,6) and (64,45,8) BCH codes
• Sufficient Conditions for Ruling-Out Useless Iterative Steps in a Class of Iterative Decoding Algorithms (Special Section on Information Theory and Its Applications)
• The Weight Distributions of Cosets of the Second-Order Reed-Muller Code of Length 128 in the Third-Order Reed-Muller Code of Length 128
• A Method for Computing the Weight Distribution of a Block Code by Using Its Trellis Diagram (Special Section on Information Theory and Its Applications)
• An Improved Method for Formal Security Verification of Cryptographic Protocols
• A System for Deciding the Security of Cryptographic Protocols (Special Section on Cryptography and Information Security)
• A Private and Consistent Data Retrieval Scheme with Log-Squared Communication(Application,Cryptography and Information Security)
• Performance Analysis for Binary Image of Linear Block Codes over an Extended Field of GF(2)
• Adaptive Recursive Maximum Likelihood Decoding Based on the Coarsest Parallel Concatenation Decomposition : Evaluation of the Decoding Complexity by Simulation
• Soft-Input Soft-Output Decoding Algorithm Based on Iterative Minimum Distance Search for Reed-Muller Codes
• Selecting the Search Centers of h-Chase Decoding Algorithms by Simulation
• The Optimal Sectionalized Trellises for the Generalized Version of Viterbi Algorithm of Linear Block Codes and Its Application to Reed-Muller Codes
• Average Complexity Evaluation of an MLD Algorithm Using the Trellis Structure for a Linear Block Code
• Isolation of Arabidopsis thaliana cDNAs That Confer Yeast Boric Acid Tolerance
• Cloning of cDNAs Encoding Isopropylmalate Dehydrogenase from Arabidopsis thaliana and Accumulation Patterns of Their Transcripts
• Assignment of Data Types to Words in a Natural Language Specification
• Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
• RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
• Highly Boron Deficiency-Tolerant Plants Generated by Enhanced Expression of NIP5;1, a Boric Acid Channel
• An Evaluation Method of the Block Error Probability by Using a Low-Weight Sub-Trellis Diagram
• Syntactic Unification Problems under Constrained Substitutions
• A Polynomial Time Learning Algorithm for Recognizable Series
• A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
• A Note on Inadequacy of the Model for Learning from Queries
• Selection of Test Patterns in an Iterative Erasure and Error Decoding Algorithm for Non-binary Block Codes(Coding Theory)
• RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar

もっと見る 閉じる

スポンサーリンク