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

A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint" codes to be associated with the edges and vertices, respectively, of the graph. The kappa-complexity of a graphical realization is defined to be the largest dimension of any of its local constraint codes, kappa -complexity is a reasonable measure of the computational complexity of a sum-product decoding algorithm specified by a graphical realization. The main focus of this paper is on the following problem: given a linear code C and a graph G, how small can the kappa-complexity of a realization of C on G be? As useful tools for attacking this problem, we introduce the vertex-cut bound, and the notion of "vc-treewidth" for a graph, which is closely related to the well-known graph-theoretic notion of treewidth. Using these tools, we derive tight lower bounds on the kappa-complexity of any realization of C on G. Our bounds enable us to conclude that good error-correcting codes can have low-complexity realizations only on graphs with large vc-treewidth. Along the way, we also prove the interesting result that the ratio of the kappa-complexity of the best conventional trellis realization of a length-n code C to the kappa-complexity of the best cycle-free realization of C grows at most logarithmically with code length n. Such a logarithmic growth rate is, in fact, achievable.

Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs