PHYSICAL REVIEW E 81, 021104 共2010兲

Statistical mechanics of an error correcting code using monotonic and nonmonotonic
treelike multilayer perceptrons
Florent Cousseau*
Graduate School of Frontier Sciences, University of Tokyo, Chiba 277-5861, Japan

Kazushi Mimura†
Faculty of Information Sciences, Hiroshima City University, Hiroshima 731-3194, Japan

Masato Okada
Graduate School of Frontier Sciences, University of Tokyo, Chiba 277-5861, Japanand Brain Science Institute, RIKEN, Saitama 351-0198, Japan
共Received 28 September 2009; published 1 February 2010兲
An error correcting code using a treelike multilayer perceptron is proposed. An original message s0 is
encoded into a codeword y0 using a treelike committee machine 共committee tree兲 or a treelike parity machine
共parity tree兲. Based on these architectures, several schemes featuring monotonic or nonmonotonic units are
introduced. The codeword y0 is then transmitted via a binary asymmetric channel where it is corrupted bynoise. The analytical performance of these schemes is investigated using the replica method of statisticalmechanics. Under some specific conditions, some of the proposed schemes are shown to saturate the Shannon
bound at the infinite codeword length limit. The influence of the monotonicity of the units on the performanceis also discussed.
DOI: 10.1103/PhysRevE.81.021104

PACS number共s兲: 02.50.⫺r, 05.50.⫹q, 89.70.⫺aI. INTRODUCTION

Reliability in communication has always been a major
concern when dealing with digital data. Especially in today’s
information-dependent society, it is vital to design efficient
ways of preventing data corruption when transmitting information. Error correcting codes have been developed for thispurpose since the birth of the information theory field following the work of Shannon 关1兴.
In 1989, Sourlas derived a set of error correcting codes,
the so-called Sourlas codes, which theoretically saturate theShannon bound 关2兴. Although these codes turned out to be
impractical, the main point of interest of this paper was theparallel made between physical spin-glass systems and information theory.
Following this paper, the tools of statistical mechanics
have been successfully applied to a wide range of problems
of information theory in recent years. In the field of error
correcting codes itself 关3–5兴, as well as in spreading codes关6,7兴, and compression codes 关8–13兴, statistical mechanicaltechniques have shown great potential.
The present paper uses similar techniques to investigate
an error correcting code scheme where the codeword is encoded using treelike multilayer perceptron neural networks.
It is known that there exists a natural duality between lossy
compression codes and error correcting codes. Indeed, alossy compression code can be regarded as a standard error
correcting code, but one where the codeword is generatedusing the original decoder of the error correcting code
scheme and where the decompressed message is obtained*florent@mns.k.u-tokyo.ac.jp†

mimura@hiroshima-cu.ac.jp1539-3755/2010/81共2兲/021104共10兲

using the original encoder of the scheme 共cf. 关14兴 for details兲.
Recently, a lossy compression scheme based on a simple
perceptron decoder was investigated by Hosaka et al. 关10兴. In
their paper, they used statistical mechanical techniques toinvestigate the theoretical performance of their scheme at theinfinite codeword length limit. The perceptron they definedin their model uses a special hat-shaped nonmonotonic transfer function. This rather uncommon feature enables thescheme to deal with biased messages and it is known that
this type of function maximizes the storage capacity of thesimple perceptron 关15,16兴. They found that their scheme cantheoretically yield Shannon optimal performance. Subsequently, Shinzato et al. 关17兴 investigated the same model butin the framework of error correcting code. They found that
their model can theoretically yield Shannon optimal performance.
Based on these studies, Mimura et al. 关12兴 proposed atreelike multilayer perceptron network for lossy compression
purposes but used only the standard sign function as thetransfer function of their model. They showed that the parity
tree 共PT兲 model can theoretically yield Shannon optimal performance but only when considering unbiased messages. In
contrast, they showed that the committee tree 共CT兲 modelcannot yield optimal performance even for unbiased messages. However, the advantage of using a multilayer structure is improved replica symmetric 共RS兲 solution stability
and an increased number of codewords sharing the same distortion properties 关18兴. In a recent study, Cousseau et al. 关13兴
investigated the same treelike multilayer perceptron model
but used the hat-shaped nonmonotonic transfer function introduced by Hosaka et al. 关10兴, thus combining both advantages of 关10,12兴. By doing so, they were able to show thatboth parity tree and committee tree structures can then theoretically yield Shannon optimal performance even for biased
messages under some specific conditions.

021104-1©2010 The American Physical Society

PHYSICAL REVIEW E 81, 021104 共2010兲

COUSSEAU, MIMURA, AND OKADA

The purpose of the present paper is to discuss the performance of the same treelike perceptron models but in the error
correcting code framework, thus completing the topic of perceptron type network applications in coding theory. In thispaper, we make use of the binary asymmetric channel
共BAC兲. Indeed, the use of the nonmonotonic hat-shaped
transfer function introduced by Hosaka et al. 关10兴 enables us
to control the bias of the codeword sequence and enables therelevant schemes to deal with such an asymmetric channel
共the BAC was also used by Shinzato et al. 关17兴兲. On theother hand, we expect the schemes which use the standard
monotonic sign function to be able to deal only with thebinary symmetric channel 共BSC兲. which corresponds to aparticular case of the BAC. The majority of popular error
correcting codes such as turbo codes 关19兴 and low-density
parity check codes 共LDPCs兲 关20,21兴, which provide near Shannon performance in practical time frames, have been
widely studied but this was generally restricted to symmetricchannels. On the other hand, apart from a few studies
关22,23兴, little is known when dealing with asymmetric channels.
Multilayer perceptrons have been widely studied over theyears by the machine learning community and a wide rangeof problems have been considered 共storage capacity, learning
rules, etc.兲. These works revealed nontrivial behaviors ofeven simple models such as the simple perceptron network,for example. Many of these previous results are summarized
in Ref. 关24兴. The present analysis gives us an opportunity to
discuss the difficulty of decoding for densely connected systems 共or dense systems as opposed to sparsely connected
systems such as LDPC codes for example兲 using a systematic manner in the context of multilayer networks. There has
been relatively little discussion of dense systems mainly because of the computational cost which is obviously higher
than for sparse systems. However, because of their rich randomness, dense systems can possibly be regarded as pseudorandom codes such as the dense limit of LDPC codes.
In this paper we mainly focus on the necessary conditions
to get Shannon optimal performance. To discuss practical
decoders, it is first necessary to investigate the optimality of
our schemes. This includes discussion of the optimal parameters for the transfer function since we need to know theseparameters to discuss the optimal decoder. In other words,
we need a theoretical analysis of the performance before wecan study the decoding problem.
The paper is organized as follows. Section II introduces
the framework of error correcting codes. Section III describes our model. Section IV deals with the BAC capacity.
Section V presents the mathematical tools used to evaluate
the performance of the present scheme. Section VI states theresults and elucidates the location of the phase transition,
which characterizes the best achievable performance of themodel. Section VII is devoted to the conclusion and discussion.
II. ERROR CORRECTING CODES

In a general scheme, an original message s0 of size N is
encoded into a codeword y0 of size M by some encoding

y0=-1

1-r

y=-1

r
p

y0=1

y=1

1-p

FIG. 1. The binary asymmetric channel 共BAC兲.

device. The aim of this stage is to add redundancy to theoriginal data. Therefore, we necessarily have M ⬎ N. Basedon this redundancy, a proper decoder device should be able
to recover the original data even if it were corrupted by noisein the transmission channel. The quantity R = N / M is called
the code rate and evaluates the trade-off between redundancy
and codeword size. The codeword y0 is then fed into a channel where the bits are subject to noise. The received noisy
message y 共which is also M dimensional兲 is then decodedusing its redundancy to infer the original N dimensional message s0. In other words, in a Bayesian framework, one tries tomaximize the following posterior probability:
P共s兩y兲 ⬀ P共y兩s兲P共s兲.

共1兲

As data transmission is costly, generally one wants to be able
to ensure error-free transmission while transmitting the fewest possible bits. In other words, one wants to ensure errorfree transmission while keeping the code rate as large as
possible. For this purpose, the well-known Shannon bound关1兴 gives a way to compute the best achievable code rate
which allows error-free recovery. However, while this gives
us the value of such an optimal code rate, it does not giveany clue as to how to construct such an optimal code. Therefore, several codes have been proposed over the years in an
ongoing quest to find a code which can reach this theoreticalbound.
III. ERROR CORRECTING CODES USING MONOTONICAND NONMONOTONIC MULTILAYER PERCEPTRONSIn this paper, since we make use of techniques derived
from statistical mechanics, we will use Ising variables rather
than Boolean ones. The Boolean 0 is mapped onto 1 in the
Ising framework while the Boolean 1 is mapped to −1. This
mapping can be used without any loss of generality.
We assume that the original message s0 is generated fromthe uniform distribution and that all the bits are independently generated so that we have
P共s0兲 =

1
.
2N

共2兲

The channel considered in this study is the BAC where each
bit is flipped independently of the others with asymmetricprobabilities. If the original bit fed into the channel is 1, thenit is flipped with probability p. Conversely, if the original bit
is −1, it is flipped with probability r. Figure 1 shows the
BAC properties in details.
The well-known BSC corresponds to the particular caser = p.
When the corrupted message y is received at the output of
the channel, the goal is then to recover s0 using y. The state021104-2

STATISTICAL MECHANICS OF AN ERROR CORRECTING …

PHYSICAL REVIEW E 81, 021104 共2010兲

Channel noisey0sReceivedmessage(size M)

Estimatedmessage(size N)+

Codeword(size M)

µ

Xl

sK0

...

s0l

...

s
...

Original
message(size N)yFIG. 2. Layout of the scheme.
µof the estimated message is denoted by the vector s. The
general outline of the scheme is shown in Fig. 2.
From Fig. 1 we can easily derive the following conditional probability:
P共y ␮兩y 0␮兲 =1 y␮+ 关共1 − r − p兲y 0␮ + 共r − p兲兴,
2 2

M

␮=1

再

冎

1 y␮
+ 关共1 − r − p兲y 0␮ + 共r − p兲兴 .
2 2

共4兲

To encode the original message s0 into a codeword y0, we
use three nonmonotonic treelike parity machine or committee machine neural networks 关共I兲, 共II兲, and 共III兲兴. In the sameway, we also investigate the standard monotonic parity tree
and committee tree neural networks 关共IV兲 and 共V兲兴.
共I兲 Multilayer parity tree with nonmonotonic hidden
共PTH兲 units;K

y 0␮共s0兲 ⬅ 兿 f k
l=1

冉冑

冊

K 0 ␮
s ·x .
N l l

共5兲共II兲 Multilayer committee tree with nonmonotonic hidden
共CTH兲 units;冉 冋冑 册冊K

y 0␮共s0兲 ⬅ sgn 兺 f k
l=1

K 0 ␮
s ·x
N l l

共6兲

.

Note that in this case, if the number of hidden units K iseven, it is possible to get 0 as the argument of the signfunction. We avoid this uncertainty by considering only an
odd number of hidden units for the committee tree with nonmonotonic hidden units in the sequel.
共III兲 Multilayer committee tree with a nonmonotonic output 共CTO兲 unit;冉冑 兺 冋冑
K

y 0␮共s0兲 ⬅ f k

1
sgn
K l=1

K 0 ␮
s ·x
N l l

册冊

.

共7兲

1
yµ0

uµl

K

冉冑

l=1

冊

K 0 ␮
s ·x .
N l l

共8兲

k
-1

uµK

冉冑

K

冋冑

1
兺 sgn
K l=1

K 0 ␮
s ·x
N l l

册冊

.

共9兲

In this case also, if the number of hidden units K is even, it
is a possible to get 0 as the argument of the sign function. We
again avoid this uncertainty by considering only an odd number of hidden units for the committee tree in the sequel.
The original message s0 is split into N / K-dimensional K
disjoint vectors so that s0 can be written s0 = 共s01 , . . . , sK0 兲. In
schemes 共I兲, 共II兲, and 共III兲, f k is a nonmonotonic function ofa real parameter k of the formf k共x兲 =再1

冎

if 兩x兩 ⱕ k− 1 if 兩x兩 ⬎ k,

共10兲

and the vectors xl␮ are fixed N / K-dimensional independentvectors uniformly distributed on 兵−1 , 1其. The use of random
input vectors is known to maximize the storage capacity ofperceptron networks, making such a scheme promising forerror correcting tasks. The sgn function denotes the signfunction taking 1 for x ⱖ 0 and −1 for x ⬍ 0. Each of thesearchitectures applies a different nonlinear transformation tothe original data s0. The general architecture of theseperceptron-based encoders and the nonmonotonic function f k
are displayed in Fig. 3.
Note that we can also consider an encoder based on acommittee tree where both the hidden units and the output
unit are nonmonotonic. However, this introduces an extra
parameter 共we will have one threshold parameter for the hidden units and one for the output unit兲 to tune and the performance should not change drastically. For simplicity, we restrict our study to the above three cases.
To keep the notation as general as possible, as long as
explicit use of the encoder is not necessary in computations,
we will denote the transformation performed on vector s by
the respective encoders using the following notation:
Fky 0␮共s0兲 ⬅ 兿 sgnx-ky 0␮共s0兲 ⬅ sgn

共IV兲 Multilayer PT;

共V兲 Multilayer CT;

fk(x)FIG. 3. Left: general architecture of the treelike multilayer perceptrons with N input units and K hidden units. Right: the nonmonotonic function f k.

共3兲

where we make use of the notations y0 = 共y 10 , . . . , y 0␮ , . . . , y 0M 兲
and y = 共y 1 , . . . , y ␮ , . . . , y M 兲. Since we assume that the bits areflipped independently, we deduce
P共y兩y0兲 = 兿

XK

uµ1

s01
...

0

...

µ

X1

冉再冑

K
sl · xl␮
N

冎冊

.

共11兲

Fk takes a different expression for the five different types of
network and k denotes the fact that all the encoders depend
on a real threshold parameter k 关except for schemes 共IV兲 and
共V兲, where this function does not depend on k; however for

021104-3

PHYSICAL REVIEW E 81, 021104 共2010兲

COUSSEAU, MIMURA, AND OKADA

consistency, we will keep this notation for these schemes兴.
Furthermore, note that Fk contains all the terms depending
on index l 关i.e., Fk共兵ul其兲 contains all the terms
u1 , . . . , ul , . . . , uK兴.
IV. BAC CAPACITY

In this section, we compute the capacity of the BAC. According to Shannon’s channel coding theorem, the optimalcode rate is given by the capacity of the channel. Any code
rate bigger than the channel capacity will inevitably lead to
information loss. The definition of the channel capacity C isC=

max

兵I共X,Y兲其,posterior P共s 兩 y兲. Then, let us compute the joint probabilityof y and s. We haveSince the relation between an arbitrary message s and thecodeword fed into the channel is deterministic, for any s, we
can write

冠 冉再冑

P共y兩s兲 = P y兩Fk
M

=兿

␮=1

共12兲

input probability

where I denotes mutual information, X denotes the channel
input distribution, and Y denotes the channel output distribution. Computation of the capacity of such a binary channel
requires only simple algebra and calculations are straightforward, giving
1 + ⍀C1 − ⍀C
H2共p兲 −
H2共r兲,CBAC = H2共␥C兲 −
2
2

⌬C =

冋

册

共16兲

2␥C − 1 − r + p
.
1−r−p

共17兲

In the special case r = p, the capacity simplifies to
CBSC = 1 − H2共p兲,

共18兲

which corresponds to the capacity of the BSC.
V. ANALYTICAL EVALUATIONAs stated in Sec. II, our goal is to maximize the posterior
P共s 兩 y兲. Let us define the following Hamiltonian:
H共y,s兲 = − ln关P共s兩y兲P共s兲兴 = − ln P共y,s兲.

共19兲

The ground state of the above Hamiltonian trivially corresponds to the maximum a posteriori 共MAP兲 estimator of theK兺q,q̂,m,m̂ y=⫾1 −⬁ l=1

+R

冕

⬁

兿 DRl

1 y␮
+
共1 − r − p兲Fk
2 2

冉再冑

K
sl · xl␮
N

冎冊
共21兲

.

冋 再 再
冉再冑 冎冊 冎冎册M1= − ln N 兿
2 ␮=1

1 y␮
共1 − r − p兲+2 2K
sl · xl␮
N⫻Fk+ 共r − p兲.

共22兲

Using this Hamiltonian, we can define the following partition
function:
Z共␤,y,x兲 = 兺 exp关− ␤H共y,s兲兴,

共23兲

where the sum over s represents the sum over all possible
states for vector s, and ␤ is the inverse temperature parameter. Such a partition function can be identified with the partition function of a spin-glass system with dynamical variables s and quenched variables x. The average of thispartition function over y and x naturally contains all the interesting typical properties of the scheme, such as the freeenergy. However, it is hard to evaluate this average and weneed some techniques to investigate it. In this paper, we use
the so-called replica method to calculate the average of thepartition function. Once the free energy is obtained, one cancompute the critical code rate at which a phase transition
occurs between the ferromagnetic phase 共error recovery possible兲 and the paramagnetic phase 共decoding impossible兲.
This gives us the best code rate the scheme can achieve. A
code rate exceeding this critical value will make decoding
impossible. The calculations to obtain the average of the partition function 具Z共␤ , y , x兲典y,x are detailed in Appendix.
After long calculations, the RS free energy is obtained,

再 冕 冉 冊冕 冉 冊⬁− f RS共q,q̂,m,m̂兲 = extr,s

rr共1 − r兲1−r 1/1−r−p,p p共1 − p兲1−p

⍀C =

冎冊冡

H共y,s兲 = − ln P共y,s兲

共13兲

共15兲

K
sl · xl␮N

We finally get the explicit expression of the Hamiltonian,

共14兲

1
1
␥C =
= 关共1 − p兲共1 + ⍀C兲 + r共1 − ⍀C兲兴,
1 + ⌬C 2

再 冋
册冎+ 共r − p兲

where
H2共x兲 = − x log2共x兲 − 共1 − x兲log2共1 − x兲,

共20兲

P共y,s兲 = P共y兩s兲P共s兲.

⬁

K

冉

1

y

兿 Dtl ln关I共y,Rl,tl,m,q兲兴 2 + 2 兵共1 − r − p兲Fk共兵Rl其兲 + 共r − p兲其−⬁ l=1

DU ln关2 cosh共冑q̂U + m̂兲兴 − R ln 2 − Rmm̂ − R−⬁

021104-4冎q̂共1 − q兲
,
2

冊
共24兲

STATISTICAL MECHANICS OF AN ERROR CORRECTING …

where
I共y,Rl,tl,m,q兲 =冕 冋兿 册
⬁

K

再

l=1

−⬁

⫻

共32兲

Dzl

1 y
y
+ 共r − p兲 + 共1 − r − p兲Fk共兵冑1 − qzl
2 2
2

冎

共25兲

2

e−x /2共26兲

冑2␲ dx.

Dx =and where extr denotes extremization. The sum denotes thesum other all possible states for the variable y, that is, ⫾1.
Note also that we set ␤ = 1. This choice of finite temperature decoding 共in contrast to ␤ → ⬁ which corresponds to thezero temperature limit兲 corresponds to the maximizer of posterior marginals 共MPMs兲 estimator, while the zero temperature decoding corresponds to the MAP estimator 关25,28兴.
The MPM estimator is known to be optimal for the purposeof decoding 关26–28兴. On top of that, in this paper we suppose that all the channel properties 关i.e., the true values of
共p , r兲兴 are known to the decoder which implies that the system’s state we consider is located on the Nishimori line
关26,27兴.
To retrieve the free energy one has to extremize Eq. 共24兲with respect to the order parameters q , q̂ , m , m̂. This is doneby solving the following saddle-point equations:⳵ f RS= 0 ⇔ q̂ = − 2R−1 兺⳵qy=⫾1冕 冋兿 册冕 冋兿 册
⬁

K

−⬁

l=1

⬁

K

−⬁

l=1

DRl

冉

冊

⳵ f RS= 0 ⇔ m̂ = R−1 兺
⳵m
y=⫾1

冕冋
−⬁

K

兿 DRl
l=1

册冕 冋 册
⬁−⬁I⬘ 共y,Rl,tl,m,q兲⫻ m
I共y,Rl,tl,m,q兲冕⳵ f RS
=0⇔m=
⳵ m̂

⬁

共33兲

l=1

Using this encoder function and substituting m = q = 0 in thesaddle-point equations, one can find a consistent solution
where q = m = q̂ = m̂ = 0. This corresponds to the paramagnetic
solution, where decoding of the received message fails. Using these conditions in Eq. 共24兲, one can retrieve the freeenergy of the paramagnetic phase,再冎1
关共1 − p兲共1 + ⍀ PTH兲 + r共1 − ⍀ PTH兲兴 ⫻ ln 2,
2
共34兲

where

兿 Dtl

l=1

冕

+⬁

Dzl f k共zl兲.

共35兲

−⬁

l=1

共28兲

DU tanh2共冑q̂U + m̂兲,

共29兲

DU tanh共冑q̂U + m̂兲,共30兲

⳵ I共y,Rl,tl,m,q兲
,
⳵q

共31兲

−⬁

where
Iq⬘共y,Rl,tl,m,q兲 =Fk共兵ul其兲 = 兿 f k共ul兲.

K

冊

⬁

K

⍀ PTH = 兿−⬁冕Using a parity tree with nonmonotonic hidden units 关Eq.
共5兲兴, the encoder function becomesK

1 y+ 兵共1 − r − p兲Fk共兵Rl其兲 + 共r − p兲其 ,2 2

⳵ f RS=0⇔q=
⳵ q̂

A. Replica symmetric solution using a parity treewith nonmonotonic hidden units− f para = − H2

共27兲

+ 共r − p兲其 ,⬁An error correcting code scheme typically admits two solutions: one where m = q = 1, called the ferromagnetic solution
and one where m = q = 0, called the paramagnetic solution. As
the names indicate, these solutions come from the physicalferromagnet state and correspond to the case where the spinsare all ordered 共m = q = 1兲 or to the case where the spins takecompletely random states 共m = q = 0兲. As we can deduce from
Eqs. 共A3兲 and 共A6兲, the ferromagnetic solution corresponds
to decoding success since m = 1 implies perfect overlap. Conversely, the paramagnetic phase implies failure in the decoding process 共overlap m is 0兲.

DtlI⬘共y,Rl,tl,m,q兲
1 y
⫻
⫻ q
+ 兵共1 − r − p兲Fk共兵Rl其兲
2 2
I共y,Rl,tl,m,q兲冉⳵ I共y,Rl,tl,m,q兲.
⳵m⬘ 共y,Rl,tl,m,q兲 =Im+ 冑q − m2tl + mRl其兲 ,⫻PHYSICAL REVIEW E 81, 021104 共2010兲

In the same way, substituting m = q = 1 in the saddle-point
equations, one can find a consistent solution. However, theferromagnetic solution cannot be computed analytically. So
we proceed numerically by simply checking the integrand of
Eqs. 共27兲 and 共28兲. We did that extensively for values of K
= 1, K = 2, and K = 3. In each case we found that the integranddiverges so that when 共q , m兲 → 共1 , 1兲, we have both q̂ → ⬁and m̂ → ⬁. Substituting q̂ → ⬁ and m̂ → ⬁ into Eqs. 共29兲 and共30兲 clearly yields q = m = 1. So q = m = 1, q̂ → ⬁, and m̂ → ⬁ isa consistent solution of the saddle-point equations which corresponds to the ferromagnetic solution, where decoding of
the received message succeeds. We also checked higher values of K 共up to K = 5兲 and did not find any other consistentsolution. We conjecture that this result holds for any finite
value of K. Finally, substituting m = q = 1, m̂ → ⬁, and q̂ → ⬁into Eq. 共24兲, one can get the free energy of the ferromagnetic phase,

021104-5

PHYSICAL REVIEW E 81, 021104 共2010兲

COUSSEAU, MIMURA, AND OKADA− f ferro = −Fk共兵ul其兲 = f k
共36兲− R ln 2.

Note that when K = 1, the present scheme corresponds to thecase of Shinzato et al. 关17兴. The result we obtained whenK = 1 is indeed equivalent to what they found.
B. Replica symmetric solution using a committee treewith nonmonotonic hidden units

When a committee tree with nonmonotonic hidden units关Eq. 共6兲兴 is used, the encoder function becomes冋兺 册
K

Fk共兵ul其兲 = sgn

f k共ul兲 .

共37兲

l=1

Using this encoder function and substituting m = q = 0 in thesaddle-point equations, one can find a consistent solution
where q = m = q̂ = m̂ = 0. This corresponds to the paramagnetic
solution, where decoding of the received message fails. Using these conditions in Eq. 共24兲, one can retrieve the freeenergy of the paramagnetic phase,− f para = − H2

再冎⍀CTH =

冕 冋兿 册
+⬁

K

−⬁

l=1

冋兺 册

f k共zl兲 .

共39兲

l=1

In the same way, by substituting m = q = 1 in the saddle-point
equations one can find a consistent solution. However, theferromagnetic solution cannot be computed analytically, so
we proceed numerically by simply checking the integrand of
Eqs. 共27兲 and 共28兲. We did that extensively for K = 3 共weconsider only odd values of K for this scheme and when K= 1 the present scheme is equivalent to the parity tree case兲.
We found that the integrand diverges so that when 共q , m兲
→ 共1 , 1兲, we have both q̂ → ⬁ and m̂ → ⬁. We also checkedhigher values of K 共up to K = 5兲 and did not find any otherconsistent solution. We conjecture that this result holds forany finite value of K. Finally, substituting m = q = 1, m̂ → ⬁,and q̂ → ⬁ into Eq. 共24兲, one can get the free energy of theferromagnetic phase,− f ferro = −ln 2
关共1 + ⍀CTH兲H2共p兲 + 共1 − ⍀CTH兲H2共r兲兴
2− R ln 2.

共40兲

C. Replica symmetric solution using a committee treewith a nonmonotonic output unit

When a committee tree with a nonmonotonic output unit关Eq. 共7兲兴 is used, the encoder function becomes

共41兲

D. Replica symmetric solution using a parity tree

Using a parity tree 关Eq. 共8兲兴, the encoder function becomesK

Fk共兵ul其兲 = 兿 sgn共ul兲.

共42兲

l=1

共38兲

K

Dzl ⫻ sgn

1
sgn共ul兲 .
K l=1

Using this encoder function and substituting m = q = 0 in thesaddle-point equations do not imply m̂ = q̂ = 0 and a nontrivial
solution is found, which makes the free energy too complex
to be investigated. This scheme is likely to give nonoptimal
performance in such a case and will not be considered inwhat follows.
Note that the limit where K → ⬁ was not studied because
the saddle-point equations take a nontrivial form that is difficult to investigate 共in the lossy compression case, this study
is still tractable兲. The techniques to investigate the free energy in the K → ⬁ limit described in Ref. 关24兴 cannot beeasily applied here. However, based on the previous resultsof Cousseau et al. 关13兴, it is probable that in the K → ⬁ limit,
the committee tree with a nonmonotonic output unit saturates
the Shannon bound in the general BAC case.

1关共1 − p兲共1 + ⍀CTH兲 + r共1 − ⍀CTH兲兴 ⫻ ln 2,
2

where

冋冑 兺 册
K

ln 2
关共1 + ⍀ PTH兲H2共p兲 + 共1 − ⍀ PTH兲H2共r兲兴
2

Using this encoder function and substituting m = q = 0 in thesaddle-point equations, one can find a consistent solution
where q = m = q̂ = m̂ = 0 but only when K ⬎ 1. This corresponds
to the paramagnetic solution, where decoding of the received
message fails. Using these conditions in Eq. 共24兲, one canretrieve the free energy of the paramagnetic phase,− f para = − H2

再冎1关共1 − p兲共1 + ⍀ PT兲 + r共1 − ⍀ PT兲兴 ⫻ ln 2,
2
共43兲

where
K

⍀ PT = 兿
l=1

冕

+⬁

Dzl ⫻ sgn共zl兲.

共44兲

−⬁

When K = 1 is considered, m = q = 0 does not imply m̂ = q̂ = 0
and a nontrivial solution is found that makes the free energy
too complex to be investigated. The scheme is likely to givenonoptimal performance in such a case and will not be considered in what follows.
In the same way, substituting m = q = 1 in the saddle-point
equations, one can find a consistent solution but only whenK ⬎ 1. However, the ferromagnetic solution cannot be computed analytically, so we proceed numerically by simply
checking the integrand of Eqs. 共27兲 and 共28兲. We did that
extensively for values of K = 2 and K = 3. In each case, we
found that the integrand diverges so that when 共q , m兲
→ 共1 , 1兲 we have both q̂ → ⬁ and m̂ → ⬁. We also checkedhigher values of K 共up to K = 5兲 and did not find any other021104-6

STATISTICAL MECHANICS OF AN ERROR CORRECTING …

PHYSICAL REVIEW E 81, 021104 共2010兲

consistent solution. We conjecture that this result holds forany finite value of K ⬎ 1. Finally, substituting m = q = 1, m̂
→ ⬁, and q̂ → ⬁ into Eq. 共24兲, one can get the free energy ofthe ferromagnetic phase,

phase兲. In other words, this enables us to calculate the optimal code rate for each scheme. At the phase transition point,
we havef para = f ferro .

共49兲

1+⍀
1−⍀
H2共p兲 −
H2共r兲,
2
2

共50兲

ln 2
− f ferro = −关共1 + ⍀ PT兲H2共p兲 + 共1 − ⍀ PT兲H2共r兲兴 − R ln 2.
2

Simple algebra leads to

共45兲

R = H 2共 ␥ 兲 −where

E. Replica symmetric solution using a committee tree

Using a committee tree 关Eq. 共9兲兴, the encoder function
becomes冋冑 兺
K

Fk共兵ul其兲 = sgn册1
sgn共ul兲 .
K l=1

共46兲

Using this encoder function and substituting m = q = 0 in thesaddle-point equations do not imply m̂ = q̂ = 0 and a nontrivial
solution is found that makes the free energy too complex to
be investigated. This scheme is likely to give nonoptimal
performance in such a case and will not be considered inwhat follows. As in the lossy compression case 关12兴, thecommittee tree is unable to yield Shannon optimal performance.
Note that the limit where K → ⬁ was not studied because
the saddle-point equations take a nontrivial form that is difficult to investigate 共in the lossy compression case, this study
is still tractable兲. The techniques to investigate the free energy in the K → ⬁ limit described in reference 关24兴 cannot beeasily applied here. However, based on the previous resultsof Mimura et al. 关12兴, it is probable that in the K → ⬁ limit
the committee tree still fails to saturate the Shannon boundeven in the BSC case.

1␥ = 关共1 − p兲共1 + ⍀兲 + r共1 − ⍀兲兴2

共51兲

and where ⍀ is given by the encoder considered 共⍀ PTH,
⍀CTH, or ⍀ PT兲. This equation has exactly the same form as
the BAC capacity Eq. 共13兲 and in fact is equivalent to the
BAC capacity if and only if ⍀ = ⍀C. Since ⍀ depends on theencoder, we will treat each case in the following subsections.
A. Tuning of the parity tree with nonmonotonic
hidden units

In the parity tree with nonmonotonic hidden units case,
we haveK⍀ ⬅ ⍀ PTH = 兿
l=1

冕

+⬁

Dzl f k共zl兲.

共52兲

−⬁

The parity tree with nonmonotonic hidden units is optimal if
and only if
1K⍀ PTH = ⍀C ⇔ H共k兲 = 共1 − 冑⍀C兲,
4

共53兲

冕

共54兲

where
VI. PHASE TRANSITION

For the parity and committee tree with nonmonotonic hidden units and for the standard parity tree, we found a paramagnetic and a ferromagnetic solution of the following form:− f para = − H2

− f ferro = −再冎1关共1 − p兲共1 + ⍀兲 + r共1 − ⍀兲兴 ⫻ ln 2,
2
共47兲

ln 2
关共1 + ⍀兲H2共p兲 + 共1 − ⍀兲H2共r兲兴 − R ln 2,2
共48兲

where ⍀ is given by ⍀ PTH, ⍀CTH, or ⍀ PT depending on theencoder considered.
It then becomes possible to calculate the critical value ofthe code rate R at which a sharp phase transition occurs
between the ferromagnetic and the paramagnetic phase. This
indicates the boundary between possible decoding 共ferromagnetic phase兲 and impossible decoding 共paramagnetic

H共x兲 =+⬁

Dz.

xThis gives us a condition on the threshold parameter k of thenonmonotonic transfer function f k. If the threshold k is tuned
to satisfy Eq. 共53兲, the scheme achieves the Shannon limit.
The only remaining issue is whether such an optimal threshold k exists.
We solved Eq. 共53兲 numerically with parameters 共p , r兲
苸 兵兴0 , 1关其2 and always found an optimal threshold parameterk up to K = 11. Note that ⍀C can be negative, which causes
problems for the Kth root when considering an even numberof hidden units K. However a simple permutation of theprobability p and r changes the sign of ⍀C. Since the original
messages are drawn from the uniform distribution, this permutation can be done without any loss of generality. Insteadof using s0, one uses −s0. We did not check higher values ofK, but we conjecture that the same result holds. This meansthat the parity tree with nonmonotonic hidden units saturates
the Shannon bound in the large codeword length limit for
any number of hidden units K.

021104-7

PHYSICAL REVIEW E 81, 021104 共2010兲

COUSSEAU, MIMURA, AND OKADA
B. Tuning of the committee treewith nonmonotonic hidden units

In the committee tree with non monotonic hidden units
case, we have冕 冋+⬁⍀ ⬅ ⍀CTH =−⬁册 冋兺 册

K

兿 Dzl ⫻ sgn
l=1

K

f k共zl兲 .

共55兲

l=1

The committee tree with nonmonotonic hidden units is optimal if and only if
K−1
2⍀CTH = ⍀C ⇔ ⍀C = 兺
l=0

冉冊

K
兵关2H共k兲兴l关1 − 2H共k兲兴K−ll− 关2H共k兲兴K−l关1 − 2H共k兲兴l其,共56兲

where 共 yx 兲 denotes the binomial coefficient. This gives us acondition on the threshold parameter k of the nonmonotonic
transfer function f k. If the threshold k is tuned to satisfy Eq.
共56兲, the scheme achieves the Shannon limit. Thus, weshould check if such an optimal threshold k exists.
We solved Eq. 共56兲 numerically with parameters 共p , r兲
苸 兵兴0 , 1关其2 and always found an optimal threshold parameterk up to K = 11. We did not check higher values of K, but we
conjecture that the same result holds. Note that as mentioned
in the definition of this encoder, we considered only an odd
number of hidden units K. Therefore, these results mean thatthe committee tree with nonmonotonic hidden units saturates
the Shannon bound in the large codeword length limit for
any odd number of hidden units K.
C. Tuning of the parity tree

In the parity tree case, we haveK⍀ ⬅ ⍀ PT = 兿
l=1

冕

+⬁

Dzl ⫻ sgn共zl兲.

共57兲

−⬁

The parity tree is optimal if and only if⍀ PT = ⍀C ⇔ ⍀C = 0.

共58兲This gives us a strong condition on ⍀C. From the definition
共17兲, it can be easily seen that ⍀C = 0 if and only if r = p: thatis when the BAC channel turns into the particular case of the
BSC channel. This means that the standard monotonic parity
tree saturates the Shannon bound in the large codeword
length limit, but only in the BSC case and for a number ofhidden units K ⬎ 1. This confirms what we expected and is
the equivalent of Mimura et al. 关12兴 lossy compression case.
VII. CONCLUSION AND DISCUSSION

We investigated an error correcting code scheme for uniformly unbiased Boolean messages using parity tree andcommittee tree multilayer perceptrons. All the schemes
which use the nonmonotonic transfer function f k in theirhidden layer were shown to saturate the Shannon bound under some specific conditions. The use of f k enables the relevant schemes to deal with asymmetric channels such as the
BAC while monotonic networks using only the standard signfunction can deal only with symmetric channels such as the
BSC.
Indeed, we confirmed that the standard monotonic parity
tree saturates the Shannon bound only in the case of the BSC
channel. The standard monotonic committee tree, however,fails to provide optimal performance even in the BSC case.
As a general conclusion, this paper shows that treelike
multilayer perceptrons introduced in 关10,12,13兴 within theframework of lossy compression can also be used efficiently
in an error correcting code scheme. For each network considered, we provided a theoretical analysis of the typical performance and gave the necessary conditions for obtaining
optimal performance. In each case, we were able to derive
results similar to the lossy compression results. Finally, inthe case of error correcting code, the replica symmetric solution stability 关18兴 was not checked because no replica symmetry breaking is expected on the Nishimori line 关29兴.
This paper discusses only the typical performance of theschemes at the infinite codeword length, however, and does
not provide any explicit decoder. Because the present
schemes make use of densely connected systems, a formal
decoder cannot be implemented as it would require a decoding time which would grow exponentially with the size ofthe original message. One promising alternative is to use thepopular belief propagation 共BP兲 algorithm to calculate an
approximation of the marginalized posterior probabilities.
The BP algorithm is known for giving good results whenworking in the ferromagnetic phase, where no frustration ispresent into the system.
With the previous work done on lossy compression
关10,12,13,30兴 and on error correcting code 关17兴 using perceptron type networks, there is now a sufficient theoretical background to investigate and compare the practical performance
共in the finite codeword length limit兲 of all the schemes withthe theoretical performance. In the case of lossy compression
with a simple perceptron, the study of the BP algorithm performance has already been done by Hosaka et al. 关30兴. Theirwork provides a solid base from which to begin investigating
the more complicated multilayer structure. The influence ofthe number of hidden units on the practical performance ofthe scheme is an interesting issue which will be examined infuture work.

ACKNOWLEDGMENTS

This work was partially supported by a Grant-in-Aid for
Encouragement of Young Scientists 共B兲 共Grant No.
18700230兲, Grant-in-Aid for Scientific Research on Priority
Areas 共Grants No. 18079003 and No. 18020007兲, Grant-inAid for Scientific Research 共C兲 共Grant No. 16500093兲, and a
Grant-in-Aid from JSPS Foundations 共Grant No. 06J06774兲
from the Ministry of Education, Culture, Sports, Science andTechnology of Japan.

021104-8

STATISTICAL MECHANICS OF AN ERROR CORRECTING …

PHYSICAL REVIEW E 81, 021104 共2010兲
n

APPENDIX: ANALYTICAL EVALUATIONUSING THE REPLICA METHOD

1
具Z共␤,y,x兲n典y,x − 1lim␤N n→0n

共A1兲

Vector sa is given by sa = 共sa1 , . . . , sKa兲 and superscript a denotes the replica index.
We proceed to the calculation of the replicated partition
function 共A2兲. Inserting the following two identities:

where Z共␤ , y , x兲n denotes the n-times replicated partition
function

n

K

1=兿兿
a=1 l=1

冕冉+⬁dmal ␦ s0l · sal −−⬁冊 冉 冊 冕 冉兿 兿

1 nK
N a
ml =
K
2␲i

l

a

冊 冋

K

1= 兿 兿
a⬍b l=1

冕

冉

+⬁

a
b
dqab
l ␦ sl · sl −

−⬁

冊冉 冊

1 n共n−1兲K/2
N ab
ql =
K
2␲i

冉

dmal dm̂al exp 兺 兺 m̂al s0l · sal −

and
n

共A2兲

s1,. . .,sn

The free energy can be evaluated by the replica method,f共␤,R兲 = −兿 exp兵− ␤H关y,ŷ共sa兲兴其.
兺 a=1

Z共␤,y,x兲n =冕 冉兿 兿

a

l

N a
m
K l

冊 冋兺 兺 冉abdqab
l dq̂l exp

a⬍b l

冊册

N ab
q
K l

q̂ab
sal · sbl −
l

a⬍b l

共A3兲

冊册

共A4兲

into Eq. 共A2兲 enables us to separate the relevant order parameters and to calculate the average moment 具Z共␤ , y , x兲n典y,x fornatural numbers n as
具Z共␤,y,x兲n典y,x ⯝冕冉兿 兿 dmal⫻

1 y+ 关共1 − r − p兲Fk共兵Rl其兲 + 共r − p兲兴
2 2

冉

a

l

dm̂al
2␲i

再 冋
再兺 冋兺

冊冕 冉

兿 兿 dqabla⬍b l

冊 再 冋 再兺 冕 冉兿冊兿 再 冋 冉
册冎冎

dq̂ab
l
exp N R−1 ln
2␲iexp ␤ ln

a

y

l

dul

dvl
dWl
dRl
2␲
2␲

1 y
+ 关共1 − r − p兲Fk共兵ual 其兲 + 共r − p兲兴
2 2

11⫻ 兿 exp − 共Wl兲2 − vl · Ql · vl − WlMl · vl + iRlWl + ivl · ul
2
2
l
+

1
ln
K

exp

sa

a,l

a b
m̂al sal + 兺 q̂abl sl sla⬍b,lwhere Ql is an n ⫻ n matrix having elements 兵qabl 其 and where
Ml is an n dimensional vector having elements 兵mal 其. We
analyze the scheme at the thermodynamic limit N , M → +⬁while the code rate R is kept finite. In this limit, Eq. 共A5兲 canbe evaluated using the saddle-point method with respect toabma , m̂a , qab
l , q̂l so that the free energy can be retrieved. To
continue the calculation, we have to make some assumptions
about the structure of these order parameters. In this paper,
we use the so-called replica symmetric 共RS兲 ansatz,
mal = m,qabl = 共1 − q兲␦ab + q,

关1兴 C. E. Shannon, Bell Syst. Tech. J. 27, 379 共1948兲.
关2兴 N. Sourlas, Nature 共London兲 339, 693 共1989兲.
关3兴 Y. Kabashima, T. Murayama, and D. Saad, Phys. Rev. Lett.
84, 1355 共2000兲.

册冎

−

冊

1
1
兺 mam̂a − 兺 qabq̂ab − ␤ 兺a ln 2
K a,l l l K a⬍b,l l lm̂al = m̂,

册冎

,

q̂ab
l = 共1 − q̂兲␦ab + q̂,

冊册冎
共A5兲

共A6兲

where ␦ab denotes the Kronecker delta. This ansatz meansthat all the hidden units are equivalent after averaging overthe disorder.
Also note that by definition, order parameter m is equivalent to quantity s0 · s / N, which gives the overlap between the
decoded message s and the original message s0. An overlapof 1 indicates perfect decoding while an overlap of 0 denotes
complete failure.

关4兴 H. Nishimori and K. Y. Michael Wong, Phys. Rev. E 60, 132
共1999兲.
关5兴 A. Montanari and N. Sourlas, Eur. Phys. J. B 18, 107 共2000兲.
关6兴 T. Tanaka, Europhys. Lett. 54, 540 共2001兲.

021104-9

PHYSICAL REVIEW E 81, 021104 共2010兲

COUSSEAU, MIMURA, AND OKADA
关7兴 T. Tanaka and M. Okada, IEEE Trans. Inf. Theory 51, 700
共2005兲.
关8兴 T. Murayama and M. Okada, J. Phys. A 36, 11123 共2003兲.
关9兴 T. Murayama, Phys. Rev. E 69, 035105共R兲 共2004兲.
关10兴 T. Hosaka, Y. Kabashima, and H. Nishimori, Phys. Rev. E 66,
066126 共2002兲.
关11兴 T. Hosaka and Y. Kabashima, J. Phys. Soc. Jpn. 74, 488
共2005兲.
关12兴 K. Mimura and M. Okada, Phys. Rev. E 74, 026108 共2006兲.
关13兴 F. Cousseau, K. Mimura, T. Omori, and M. Okada, Phys. Rev.
E 78, 021124 共2008兲.
关14兴 D. J. C. MacKay, Information Theory, Inference, and Learning
Algorithms 共Cambridge University Press, Cambridge, England,
2003兲.
关15兴 R. Monasson and D. O’Kane, Europhys. Lett. 27, 85 共1994兲.
关16兴 G. J. Bex, R. Serneels, and C. Van den Broeck, Phys. Rev. E
51, 6309 共1995兲.
关17兴 T. Shinzato and Y. Kabashima, Proceeding in Workshop on
Information-Based Induction Sciences 共IBIS2006兲, Osaka, Japan 共2006兲 共in Japanese兲.
关18兴 J. R. L. de Almeida and D. J. Thouless, J. Phys. A 11, 983
共1978兲.

关19兴 C. Berrou, A. Glavieux, and P. Thitimajshima, Proceedings ofIEEE International Conference on Communications 共ICC兲,1993 共unpublished兲, 1064–1070.
关20兴 R. Gallager, IRE Trans. Inf. Theory 8, 21 共1962兲.
关21兴 D. MacKay and R. Neal, Lect. Notes Comput. Sci. 1025, 100
共1995兲.
关22兴 C.-C. Wang, S. R. Kulkarni, and H. V. Poor, IEEE Trans. Inf.
Theory 51, 4216 共2005兲.
关23兴 I. Neri, N. S. Skantzos, and D. Bolla, J. Stat. Mech.: Theory
Exp. 共2008兲, 10018.
关24兴 A. Engel and C. Van den Broeck, Statistical Mechanics ofLearning 共Cambridge University Press, Cambridge, England,
2001兲.
关25兴 P. Ruján, Phys. Rev. Lett. 70, 2968 共1993兲.
关26兴 H. Nishimori, J. Phys. Soc. Jpn. 62, 2973 共1993兲.
关27兴 N. Sourlas, Europhys. Lett. 25, 159 共1994兲.
关28兴 H. Nishimori, Statistical Physics of Spin Glasses and Information Processing 共Oxford University Press, New York, 2001兲.
关29兴 H. Nishimori and D. Sherrington, in Disordered and Complex
System, edited by P. Sollich, A. Coolen, L. Hughston, and R.
Streater 共AIP, New York, 2001兲, pp. 67–72.
关30兴 T. Hosaka and Y. Kabashima, Physica A 365, 113 共2006兲.

021104-10