pith. sign in

arxiv: 1907.08063 · v1 · pith:535ONQYKnew · submitted 2019-07-18 · 💻 cs.IT · math.IT

Graph-Based Encoders and their Performance for Finite-State Channels with Feedback

Oron Sabag , Bashar Huleihel , Haim Permuter This is my paper

Pith reviewed 2026-05-24 19:27 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords finite-state channelsfeedback capacitygraph-based encoderstrapdoor channelbinary fading channelposterior matchingconvex optimizationauxiliary graphs
0
0 comments X

The pith

Graph-based encoders from auxiliary directed graphs yield new capacity results for finite-state channels with feedback.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an evaluation method that extracts graph-based encoders for unifilar finite-state channels with feedback while also producing upper bounds to test their performance. The method builds on auxiliary directed graphs to create optimization problems whose solutions give achievable rates and matching upper limits. Numerical evaluation produces near-tight bounds in multiple cases, which translate directly into exact capacity values for the non-symmetric Trapdoor channel and binary fading channels. Any feasible encoder from the method corresponds to a posterior matching coding scheme that attains the lower bound.

Core claim

By deriving simple bounds on capacity from auxiliary directed graphs, the upper bound can be recast as a convex optimization problem through a change of variables and added constraints, while any feasible point of the non-convex lower-bound problem directly supplies a valid graph-based encoder; these bounds coincide closely enough in the non-symmetric Trapdoor channel and binary fading channels to establish their capacities exactly.

What carries the argument

Auxiliary directed graphs that generate both upper bounds on capacity and feasible graph-based encoders.

If this is right

  • Exact capacity is obtained for the non-symmetric Trapdoor channel.
  • Exact capacity is obtained for binary fading channels.
  • Near-tight bounds are obtained for the Ising channel and other tested instances.
  • Every graph-based encoder yields a posterior matching scheme that achieves the computed lower bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same auxiliary-graph construction may produce capacity results for additional unifilar channels not examined in the paper.
  • The correspondence between graph encoders and posterior matching schemes suggests a route to explicit coding constructions for other feedback channels.
  • If the optimization problems remain tractable for larger state spaces, the method could scale to channels with more memory.

Load-bearing premise

A change of variables and added constraints turns the upper bound into an equivalent convex optimization problem without altering its value.

What would settle it

Explicit computation of the upper and lower bounds for the non-symmetric Trapdoor channel that produces a positive gap between them.

Figures

Figures reproduced from arXiv: 1907.08063 by Bashar Huleihel, Haim Permuter, Oron Sabag.

Figure 1
Figure 1. Figure 1: Unifilar FSC with feedback. The new channel state, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A Q-graph with |Q| = 2 and Y = {0, 1, ?}. The Q-graph is used to map channel output sequences onto unique node by walking along the labelled edges. For instance, if Q = 1 and Y = 1, then the graph will map this output to Q = 2. the lower bound, it was shown that any choice of a Q-graph yields Cfb ≥ I(X, S; Y |Q), (2) for all input distributions, PX|S,Q, that are BCJR-invariant, a property that will be defi… view at source ↗
Figure 3
Figure 3. Figure 3: A Q-graph where each node represents the last channel output (k = 1) when Y = {0, 1}. 2) Markov graphs: A valid choice of a Q-graph is a graph for which each node represents the last k output symbols. For instance, see [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The BFCs. The channel input xt is multiplied by the channel state st−1, and then a XOR operation is performed with an i.i.d. sequence Nt that is distributed according to Ber(p). where ⊕ is the XOR operation and Nt is an i.i.d. sequence that is distributed according to Ber(p) and is independent of the message. We study the following two scenarios of state evolution: 1) Type I: Channel state evaluation is gi… view at source ↗
Figure 5
Figure 5. Figure 5: Bounds on the capacity of the BFC of type [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The Q-graph which is used to obtain the graph-based encoder for the BFC of type I. DRAFT July 19, 2019 [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Bounds on the capacity of the BFC of type II. For [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 7
Figure 7. Figure 7: The first graph-based [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Upper and lower bounds on the capacity of the Ising cha [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The trapdoor channel: at time t, the channel starts with a ball st−1 already in it, and a new ball xt is inserted into the channel. The channel output yt is st−1 with probability p or xt with probability 1 − p. The new state is the remaining ball. C. The trapdoor channel The trapdoor channel was introduced by Blackwell as a “two-state simple channel” [28]. The channel is described in [PITH_FULL_IMAGE:figu… view at source ↗
Figure 10
Figure 10. Figure 10: A comparison between upper and lower bounds on the ca [PITH_FULL_IMAGE:figures/full_fig_p023_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Q-graph for the Trapdoor channel. PX|S,Q(0|0, 2) = 1 2¯p PX|S,Q(1|1, 2) = 1 2¯p PX|S,Q(0|0, 3) = p p¯ PX|S,Q(1|1, 3) = 1. where p ≤ 0.5 is the channel parameter. Straightforward calculation of the stationary distribution gives that [πS|Q(0|1), πS|Q(0|2), πS|Q(0|3)] = [ 1−2p 2(1−p) , 0.5, 1 2(1−p) ]. The BCJR equation in (6) can be written explicitly for the trapdoor channel as follows: PS+|Q+(0|g(q, y)) =… view at source ↗
read the original abstract

The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoders. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric Trapdoor channel and binary fading channels (BFCs), new capacity results are eastablished by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops an evaluation method for unifilar finite-state channels with feedback that extracts graph-based encoders and their rates via auxiliary directed graphs, formulates an upper bound as a convex optimization problem through argument transformation and constraints, and casts the lower bound as a non-convex program whose feasible points yield valid encoders. Numerical optimization yields near-tight bounds in examples; these are converted to analytic capacity expressions for the non-symmetric Trapdoor channel and binary fading channels, while near-tightness is demonstrated for the Ising channel and others by comparison with the upper bound. Any such encoder is shown to induce a posterior-matching coding scheme that achieves the lower bound.

Significance. If the optimization formulations and numerical-to-analytic conversions hold, the work supplies a practical, graph-based route to both achievable rates and upper bounds for a class of channels with memory and feedback, together with explicit encoders. The posterior-matching connection and the fact that feasible points of the lower-bound program are automatically valid encoders are concrete strengths that could be useful beyond the specific examples.

major comments (2)
  1. [Abstract] Abstract and § on Trapdoor/BFC results: the assertion that numerical near-tightness 'can be easily converted to analytic results' and thereby establishes new capacities requires an explicit derivation of the closed-form expressions; without it the central claim that exact capacities are obtained rests on an unverified step.
  2. [Method section on upper bound] Upper-bound formulation: the claim that the (possibly non-convex) upper bound 'can be formulated as a convex optimization problem using transformation of the argument with proper constraints' is load-bearing for all reported upper bounds; the manuscript must exhibit the transformed variables and prove convexity for the specific channels considered.
minor comments (2)
  1. [Abstract] Abstract: 'eastablished' is a typographical error.
  2. [Optimization formulations] Notation for the auxiliary graphs and the feasible-set constraints should be introduced with a short table or diagram to improve readability when the optimization programs are stated.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable feedback on our manuscript. We address each major comment below and outline the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract] Abstract and § on Trapdoor/BFC results: the assertion that numerical near-tightness 'can be easily converted to analytic results' and thereby establishes new capacities requires an explicit derivation of the closed-form expressions; without it the central claim that exact capacities are obtained rests on an unverified step.

    Authors: We agree that establishing exact capacities requires explicit derivations rather than relying solely on the numerical-to-analytic conversion claim. In the revised manuscript we will add dedicated subsections deriving the closed-form capacity expressions for the non-symmetric Trapdoor channel and the binary fading channels, showing how the optimizing parameters identified numerically yield the analytic formulas and confirming that the upper and lower bounds coincide. revision: yes

  2. Referee: [Method section on upper bound] Upper-bound formulation: the claim that the (possibly non-convex) upper bound 'can be formulated as a convex optimization problem using transformation of the argument with proper constraints' is load-bearing for all reported upper bounds; the manuscript must exhibit the transformed variables and prove convexity for the specific channels considered.

    Authors: We accept that the convexity argument and the explicit transformations must be shown for the channels under study. The revision will include a new subsection that defines the transformed variables, states the constraints, and provides a proof of convexity for the Trapdoor, Ising, and binary fading channels, thereby justifying all reported upper bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives graph-based encoders and capacity bounds for unifilar finite-state channels with feedback by building an evaluation method on auxiliary directed graphs. Upper bounds are reformulated as convex programs via argument transformation and constraints; lower bounds are non-convex but any feasible point directly yields a valid encoder. New analytic capacities for the non-symmetric Trapdoor channel and binary fading channels follow from solving these programs and converting numerical near-tightness. No equation or claim reduces by construction to a fitted input, self-definition, or load-bearing self-citation chain; the optimization formulations and feasible-point guarantees stand independently of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities used in the derivations.

pith-pipeline@v0.9.0 · 5737 in / 997 out tokens · 31095 ms · 2026-05-24T19:27:56.491824+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Graph-based e ncoders and their achievable rates for channels with feedba ck,

    O. Sabag, B. Huleihel, and H. H. Permuter, “Graph-based e ncoders and their achievable rates for channels with feedba ck,” in 2018 IEEE International Symposium on Information Theory (I SIT), June 2018, pp. 1121–1125

    work page 2018

  2. [2]

    Markov-based chann el characterization for tractable performance analysis in wireless packet networks,

    M. Hassan, M. M. Krunz, and I. Matta, “Markov-based chann el characterization for tractable performance analysis in wireless packet networks,” IEEE Transactions on Wireless Communications , vol. 3, no. 3, pp. 821–831, May 2004

    work page 2004

  3. [3]

    Finite-state markov channel- a useful model for radio communication channels,

    H. S. Wang and N. Moayeri, “Finite-state markov channel- a useful model for radio communication channels,” IEEE Transactions on V ehicular Technology, vol. 44, no. 1, pp. 163–171, Feb 1995. DRAFT July 19, 2019 41

    work page 1995

  4. [4]

    Capacity of a binary droplet-bas ed microfluidic channel with memory and anticipation for flow-i nduced molecular communications,

    L. Galluccio, A. Lombardo, G. Morabito, S. Palazzo, C. Pa narello, and G. Schembra, “Capacity of a binary droplet-bas ed microfluidic channel with memory and anticipation for flow-i nduced molecular communications,” IEEE Transactions on Communications, vol. 66, no. 1, pp. 194–208, Jan 2018

    work page 2018

  5. [5]

    A comprehensive survey of recent advancements in molecular communication,

    N. Farsad, H. B. Yilmaz, A. Eckford, C. Chae, and W. Guo, “A comprehensive survey of recent advancements in molecular communication,” IEEE Communications Surveys Tutorials , vol. 18, no. 3, pp. 1887–1919, thirdquarter 2016

    work page 1919

  6. [6]

    Write channel model for bit-patterned media recording,

    A. R. Iyengar, P . H. Siegel, and J. K. Wolf, “Write channel model for bit-patterned media recording,” IEEE Transactions on Magnetics , vol. 47, no. 1, pp. 35–45, Jan 2011

    work page 2011

  7. [7]

    R. G. Gallager, Information theory and reliable communication . New Y ork: Wiley, 1968

    work page 1968

  8. [8]

    On the information rate of bi nary-input channels with memory,

    D. Arnold and H. . Loeliger, “On the information rate of bi nary-input channels with memory,” in IEEE International Conference on Communications. , vol. 9, June 2001, pp. 2692–2695 vol.9

    work page 2001

  9. [9]

    A generalization of the blahutarimoto algorithm to finite-s tate channels,

    P . O. V ontobel, A. Kavcic, D. M. Arnold, and H. Loeliger, “ A generalization of the blahutarimoto algorithm to finite-s tate channels,” IEEE Transactions on Information Theory , vol. 54, no. 5, pp. 1887–1918, May 2008

    work page 1918

  10. [10]

    On the achi evable information rates of finite state isi channels,

    H. D. Pfister, J. B. Soriaga, and P . H. Siegel, “On the achi evable information rates of finite state isi channels,” in IEEE Global Telecommunications Conference , vol. 5, Nov 2001, pp. 2992–2996 vol.5

    work page 2001

  11. [11]

    Capacit y and zero-error capacity of the chemical channel with feedback,

    B. V . R. H. H. Permuter, P . Cuff and T. Weissman, “Capacit y and zero-error capacity of the chemical channel with feedback,” in Proc. International Symposium on Information Theory (ISIT ), France, Nice, 2007

    work page 2007

  12. [12]

    Feedback capac ity of finite-state machine channels,

    S. Yang, A. Kav˘ ci´ c, and S. Tatikonda, “Feedback capac ity of finite-state machine channels,” IEEE Trans. Inf. Theory , vol. 51, no. 3, pp. 799–810, Mar. 2005

    work page 2005

  13. [13]

    The capacity of channels wi th feedback,

    S. Tatikonda and S. Mitter, “The capacity of channels wi th feedback,” IEEE Trans. Inf. Theory , vol. 55, no. 1, pp. 323–349, Jan. 2009

    work page 2009

  14. [14]

    The capacity of finite-state Mark ov channels with feedback,

    J. Chen and T. Berger, “The capacity of finite-state Mark ov channels with feedback,” IEEE Trans. Inf. Theory , vol. 51, pp. 780–789, Mar. 2005

    work page 2005

  15. [15]

    Capa city of the Trapdoor channel with feedback,

    H. H. Permuter, P . Cuff, B. V . Roy, and T. Weissman, “Capa city of the Trapdoor channel with feedback,” IEEE Trans. Inf. Theory , vol. 54, no. 7, pp. 3150–3165, Jul. 2009

    work page 2009

  16. [16]

    Capacity and coding for the Ising channel with feedback,

    O. Elishco and H. Permuter, “Capacity and coding for the Ising channel with feedback,” IEEE Trans. Inf. Theory , vol. 60, no. 9, pp. 5138–5149, Sep. 2014

    work page 2014

  17. [17]

    The feedback cap acity of the binary erasure channel with a no-consecutive-o nes input constraint,

    O. Sabag, H. Permuter, and N. Kashyap, “The feedback cap acity of the binary erasure channel with a no-consecutive-o nes input constraint,” IEEE Trans. Inf. Theory , vol. 62, no. 1, pp. 8–22, Jan 2016

    work page 2016

  18. [18]

    On the capacity of the chem ical channel with feedback,

    J. Wu and A. Anastasopoulos, “On the capacity of the chem ical channel with feedback,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) , Jul. 2016, pp. 295–299

    work page 2016

  19. [19]

    On the capacity of generalized ising channels,

    A. Sharov and R. M. Roth, “On the capacity of generalized ising channels,” IEEE Trans. on Inf. Theory , vol. 63, no. 4, pp. 2338–2356, Apr. 2017

    work page 2017

  20. [20]

    Feedback capaci ty and coding for the (0, k)-RLL input-constrained BEC,

    O. Peled, O. Sabag, and H. H. Permuter, “Feedback capaci ty and coding for the (0, k)-RLL input-constrained BEC,” IEEE Transactions on Information Theory , vol. PP , pp. 1–1, 03 2019. July 19, 2019 DRAFT 42

    work page 2019

  21. [21]

    Feedback capa city and coding for the BIBO channel with a no-repeated-ones input constraint,

    O. Sabag, H. H. Permuter, and N. Kashyap, “Feedback capa city and coding for the BIBO channel with a no-repeated-ones input constraint,” IEEE Trans. on Inf. Theory , vol. 64, no. 7, pp. 4940–4961, July 2018

    work page 2018

  22. [22]

    A single-let ter upper bound on the feedback capacity of unifilar finite-st ate channels,

    O. Sabag, H. H. Permuter, and H. D. Pfister, “A single-let ter upper bound on the feedback capacity of unifilar finite-st ate channels,” IEEE Trans. Inf. Theory , vol. 63, no. 3, pp. 1392–1409, Mar. 2017

    work page 2017

  23. [23]

    Optimal feedback communica tion via posterior matching,

    O. Shayevitz and M. Feder, “Optimal feedback communica tion via posterior matching,” IEEE Trans. Inf. Theory , vol. 57, no. 3, pp. 1186–1222, Mar. 2011

    work page 2011

  24. [24]

    CVX: Matlab software for discipli ned convex programming, version 2.1,

    M. Grant and S. Boyd, “CVX: Matlab software for discipli ned convex programming, version 2.1,” http://cvxr.com/cv x, Mar. 2014

    work page 2014

  25. [25]

    Constrained s ystems and coding for recording channels,

    B. H. Marcus, R. M. Roth, and P . H. Siegel, “Constrained s ystems and coding for recording channels,” in Handbook of Coding Theory , V . S. Pless and W. C. Huffman, Eds. Amsterdam, Netherlands: Elsevier, 1998, pp. 1635–1764

    work page 1998

  26. [26]

    El Gamal and Y .-H

    A. El Gamal and Y .-H. Kim., Network Information Theory . Cambridge University Press, 2011

    work page 2011

  27. [27]

    Capacity and zero-error capac ity of Ising channels,

    T. Berger and F. Bonomi, “Capacity and zero-error capac ity of Ising channels,” IEEE Trans. Inf. Theory , vol. 36, pp. 173–180, 1990

    work page 1990

  28. [28]

    Blackwell, Information Theory

    D. Blackwell, Information Theory. Modern mathematics for the engineer: S econd series , pp. 182–193, 1961

    work page 1961

  29. [29]

    An achievable rate region f or the two-way channel with common output,

    O. Sabag and H. H. Permuter, “An achievable rate region f or the two-way channel with common output,” in 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , Oct 2018. DRAFT July 19, 2019

    work page 2018