English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider decoding of binary Tanner codes using message-passing iterativedecoding and linear programming (LP) decoding in MBIOS channels. We present newcertificates that are based on a combinatorial characterization forlocal-optimality of a codeword in irregular Tanner codes with respect to anyMBIOS channel. This characterization is based on a conical combination ofnormalized weighted subtrees in the computation trees of the Tanner graph.These subtrees may have any finite height h (even equal or greater than half ofthe girth of the Tanner graph). In addition, the degrees of local-code nodes inthese subtrees are not restricted to two. We prove that local optimality inthis new characterization implies maximum-likelihood (ML) optimality and LPoptimality, and show that a certificate can be computed efficiently.  We also present a new message-passing iterative decoding algorithm, callednormalized weighted min-sum (NWMS). NWMS decoding is a BP-type algorithm thatapplies to any irregular binary Tanner code with single parity-check localcodes. We prove that if a locally-optimal codeword with respect to heightparameter h exists (whereby notably h is not limited by the girth of the Tannergraph), then NWMS decoding finds this codeword in h iterations. The decodingguarantee of the NWMS decoding algorithm applies whenever there exists alocally optimal codeword. Because local optimality of a codeword implies thatit is the unique ML codeword, the decoding guarantee also provides an MLcertificate for this codeword.  Finally, we apply the new local optimality characterization to regular Tannercodes, and prove lower bounds on the noise thresholds of LP decoding in MBIOSchannels. When the noise is below these lower bounds, the probability that LPdecoding fails decays doubly exponentially in the girth of the Tanner graph.

On Decoding Irregular Tanner Codes with Local-Optimality Guarantees