  The reliability function of memoryless channels with noiseless feedback and
variable-length coding has been found to be a linear function of the average
rate in the classic work of Burnashev. In this work we consider unifilar
channels with noiseless feedback and study specific transmission schemes, the
performance of which provides lower bounds for the channel reliability
function. In unifilar channels the channel state evolves in a deterministic
fashion based on the previous state, input, and output, and is known to the
transmitter but is unknown to the receiver. We consider a two-stage
transmission scheme. In the first stage, both transmitter and receiver
summarize their common information in an M-dimensional vector with elements in
the state space of the unifilar channel and an M-dimensional probability mass
function, with M being the number of messages. The second stage, which is
entered when one of the messages is sufficiently reliable, is resolving a
binary hypothesis testing problem. The analysis assumes the presence of some
common randomness shared by the transmitter and receiver, and is based on the
study of the log-likelihood ratio of the transmitted message posterior belief,
and in particular on the study of its multi-step drift. Simulation results
confirm that the bounds are tight compared to the upper bounds derived in a
companion paper.
