Daniel Laskar
email: daniel.laskar@ens.fr

Ambiguity and Coordination in a Global Game Model of Financial Crises

Keywords: D81, D82, G01 Financial crises, Ambiguity, Uncertainty, Global games, Coordination, Transparency JEL classification: D81, D82, G01 financial crises, ambiguity, uncertainty, global games, coordination, transparency

We consider a two-player global game where creditors, who finance some investment project, have to decide whether to roll over their loans or not. We use a non-Bayesian approach where creditors exhibit some aversion to ambiguity. We show that an increase in ambiguity reduces the perceived coordination of players in rolling over their loans. This contibutes to increasing the probability of a financial crisis, and therefore provides an additional argument in favor of transparency in the model considered.

Introduction

The literature on financial crises has underlined that, besides the underlying state of the economy (the strength of fundamentals), the interdependence between the decisions of the participants in the financial markets may play a crucial role. These decisions may exhibit some complementarities. For example, the possibility of a bank run depends on the amount of depositors who withdraw their money deposited at the bank. In the same way, a currency crisis requires that a sufficient amount of speculators go against the currency. Also, when a group of creditors finance some investment project, a financial crisis, due to an early liquidation by creditors, occurs only when an insufficient amount of creditors roll over their loans.

As it has been shown in the literature, the presence of these complementarities between the decisions of economic agents may lead to multiple equilibria. Thus, if each one expects that other depositors withdraw their money deposited at the bank, then a bank run will occur. But such a bank run would not have occurred if, on the contrary each depositor did not expect other depositors to withdraw their money. Concerning currency crises, for some range of the values of fundamentals, a currency crisis would occur if everyone expected other participants to attack the currency, but the crisis would not occur if, on the contrary, each one expected that other participants do not attack the currency. Similarly, for some range of fundamentals, an investment failure due to an early liquidation by creditors would occur if each creditor expected that other creditors do not roll over their loans, but there would be no failure if each creditor expected that other creditors roll over their loans. In each case, the corresponding game has an equilibrium with a financial crisis, and an other one without a financial crisis [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] .

These models which lead to multiple equilibria assume that the decision makers know the relevant state variable. However, when market participants only receive imprecise signals on the relevant state variable, the literature has shown that the multiplicity of the game disappears and that a unique equilibrium emerges. In such a class of games, called "global games" in the literature [START_REF] Cheli | Self-fulfilling Currency Attacks with Biased Signals[END_REF] , where we only have one equilibrium, it becomes meaningful to do comparative statics exercises where we study the effect of changes in some exogenous parameters of the model. Furthemore, as some uncertainty is introduced in the model through the imprecision of signals, one can try to examine how the amount of uncertainty affects the equilibrium. Thus, it become possible to ask whether more uncertainty increases the probability of a financial crisis or not. According to the existing literature, the comparative statics exercises done with these models lead to ambiguous results. Depending on the parameters of the model, greater uncertainty may either increase or decrease the probability of a crisis [START_REF] Diamond | Bank Runs, Deposit Insurance, and Liquidity[END_REF] .

These results of the literature are obtained under the usual Bayesian approach to uncertainty, where each decision maker holds some prior probability distribution on unknown parameters and maximizes expected utility. However, this Bayesian approach to uncertainty has been challenged. Knight (1921) had already made the distinction between a situation of "risk" where there is a known probability distribution, and a situation of "(Knightian) uncertainty" where no known probability distribution exists. Ellsberg (1961), through some experiments, has shown that decision makers exhibit some "aversion to ambiguity". They prefer a situation where there is a known probability distribution to a situation where this distribution is unknown. This is why, in the last two or three decades, some new non-Bayesian approaches to uncertainty, where such an aversion to ambiguity could be taken into account, have been developped [START_REF] Ellsberg | Risk, Ambiguity, and the Savage Axioms[END_REF] .

Such a non Bayesian approach has been applied to a large variety of issues in economics. It has been shown that this approach could help explain some stylized facts, and could allow us to better understand some results which otherwise looked quite paradoxical [START_REF] Gajdos | Decision Making with Imprecise Probabilistic Information[END_REF] . It would therefore be worthwhile to try to apply this approach to the issue of financial crises, and more particularly to the global game models of crises.

In fact, recently, Ui (2009) has introduced such a non-Bayesian analysis in the context of global games. When applied to some standard global games models of financial crises, Ui (2009) has underlined that the effect of ambiguity may depend on the kind of model considered. Thus, in a global game model of currency attacks (as in Morris and Shin (1998)), more ambiguity appears to have a favorable role: more ambiguity tends to prevent a currency attack to occur. On the contrary, in a global game model of bank runs (Goldstein and Pauzner (2005)), ambiguity has a detrimental effect: more ambiguity increases the probability of a bank run. Kawagoe and Ui (2010) have considered ambiguity in a two player version of a global game model where some creditors have to decide whether to roll over their loan or not for some investment project (as in Morris and Shin (2004)). They show that more ambiguity has a detrimental effect: it increases the probability that the players do not roll over their loans [START_REF] Gilboa | Maximin Expected Utility with Non-Unique Prior[END_REF] .

In this paper, we will pursue this kind of analysis. We will underline that the analyses of Ui (2009) and Kawagoe and Ui (2010) actually do not give full scope to the role of ambiguity in global models of financial crises. They do not underline the role that ambiguity may have on the issue of the perceived coordination of the players, i.e. on the belief that each player has on the coordination of players. But this is crucial because of the complementarities involved. As we will emphasize, ambiguity creates a gap between the belief that each player holds on the probability distribution of the signal she receives, on the one hand, and the belief that each player holds on the probability distributions of the signals that other players receive, on the other hand. Such a difference was not allowed in the analyses of Ui (2009) and Kawagoe and Ui (2010) because it was a priori assumed that the probability distributions of the signals received by all the players were identical. In the present paper, by relaxing this assumption, we are able to underline that ambiguity may have an adverse effect on the perceived degre of coordination of the players which is held by each player.

We will use a model close to the model considered in Kawagoe and Ui (2010), which is itself inspired by Morris and Shin (2004). It is a two-player global game between two creditors who finance some investment project. At an interim stage, each player has to decide whether to roll over her loan or not.

We will show that more ambiguity decreases the degree of coordination of players which is perceived by each player when he considers rolling over her loan. This will make each player less willing to roll over the loan, and therefore makes a crisis more likely. Thus, our analysis will highlight an additional channel through which ambiguity can precipitate a financial crisis. This will reinforce the argument found in the literature that ambiguity plays a detrimental role in financial crises in such a model. As more transparency from the public authorities may reduce the amount of ambiguity that each player has to face, our results will make the case for transparency stronger in this model.

The model is presented in Section 2. Section 3 derives the equilibrium of the game. Section 4 considers the effect of more ambiguity. Section 5 concludes.

Model

As in the global game model of Morris and Shin (2004), a group of creditors are financing some investment project through some collaterized debt. At is the action with a payoff that does not depend on fundamentals. some interim stage, each creditor can either roll over the loan until the maturity of the investment project, or seize the collateral, which has some given known value λ. The value of the investment project at maturity will depend on the state of fundamentals, represented by some real variable θ. The value of fundamentals θ is not known to creditors, but each creditor receives an imperfect signal on θ. The value of the investment project at maturity will also be negatively affected if an insufficient amount of creditors do not roll over the debt. This creates some complementarities between the decisions of creditors to roll over the debt or not. The model considers the corresponding game between the creditors. As in Kawagoe and Ui (2010), we will consider a two-player version of the game, and we will introduce some ambiguity (or "Knightian uncertainty") on θ with ambiguity adverse players [START_REF] Kawagoe | Global Games and Ambiguous Information: An experimental Study[END_REF] .

The actions and payoffs of this two-player game are the following. Each player has two possible actions: to roll over the loan (R), or not to roll over the loan (N). By choosing N, the player receives the value of the collateral λ, where λ satisfies the inequality 0 < λ < 1. By choosing to roll over the loan (R), a player gets a payoff equal to 1 when the investment project succeeds, and a payoff equal to 0 when the investment project fails. It is assumed that the investment project always succeeds when the fundamentals are good enough, i.e. when we have θ > 1; and that the project always fails when the fundamentals are bad enough, i.e. when we have θ < 0. For intermediate values of the fundamentals, i.e. in the case 0 ≤ θ ≤ 1, it is assumed that the investment project succeeds only in the case where both players roll over the loan. The payoff matrix in the case 0 ≤ θ ≤ 1 (which is the case where the coordination of players matters) is therefore:

R N R 1, 1 0, λ N λ, 0 λ, λ
If the value of θ was known to the two players, then, in the case θ > 1, R would be a dominant strategy; while in the case θ < 0, N would be a dominant strategy. In the case 0 ≤ θ ≤ 1, there would however be two equilibria: a bad financial crisis equilibrium (N,N), where no player rolls over the loan and where, consequently, the inverstment project fails; and a good equilibrium without a financial crisis (R,R), where each player rolls over the loan, and where, as a consequence, the investment project succeeds.

Here, however, as in the global game literature, it is assumed that θ is not known to the players. Each player receives a signal x i given by

x i = θ + ξ i (1)
where ξ i is a random variable.

In the literature on global games, it is usually assumed that ξ i follows some given known probability distribution. It can be shown that, when we have 0 ≤ θ ≤ 1, then there is a unique equilibrium instead of the two equilibria which would have been obtained if θ was known. This occurs even when the uncertainty becomes small, i.e. when the variance of ξ i goes to zero [START_REF] Knight | Risk, Uncertainty and Profit[END_REF] .

Here, the assumption that the probability distribution of ξ i is known will be removed and it will be assumed that there is (Knightian) uncertainty, or "ambiguity", on some parameter underlying the distribution of ξ i . As indicated before, Ui (2009) and Kawagoe and Ui (2010) considered an analysis of the effect of ambiguity in global games. They assumed that ξ i followed some distribution but that the variance σ of this distribution was unkown. There was some ambiguity on the value of this variance. Each player was assumed to maximise the minimum of the expected utility, where the minimum is taken for σ belonging to some interval [σ, σ].

The crucial difference between our analysis and the analyses of Ui (2009) and Kawagoe and Ui (2010) is the following. In Ui (2009) and Kawagoe and Ui (2010), it is assumed that the probability distributions of the signal are the same for all the players. Here, we will remove such an assumption. For, each player may not necessarily get the same kind of information and may interpret an information in a different and personal way. This could change not only the signal received but also the underlying probability distribution of the signal. Thus, if there is some uncertainty on the probability distribution underlying the signal received by each player, it seems restrictive to assume that the same probability distribution underlies the signals received by all the players. It would therefore be worthwhile to consider what happens if we allow the signal received by each player to follow a probability distribution which may not be the same for all the players. This is what we will consider in our analysis. As we will see, this will permit ambiguity to have a stronger effect, because of its consequences on the perceived coordination of the players

To simplify the analysis we will also assume that it is the mean (rather than the variance) of the probability distribution of ξ i which is uncertain [START_REF] Metz | Private and Public Information in Self-Fulfilling Currency Crises[END_REF] . Thus player i receives a signal with a possible "bias" µ i , which is assumed to be uncertain 10 . We will write

ξ i = µ i + ε i (2)
where ε i is a zero-mean random variable which has a known probability distribution, and where the mean µ i of ξ i depends on i, and therefore is not necessarily the same for the two players. The random variables ε 1 and ε 2 are assumed to be stochastically independent. We therefore have

x i = θ + µ i + ε i (3)
There is ambiguity on the value of the mean (or "bias") µ i . We will assume that each µ i , i = 1, 2, belongs to the interval £ µ, µ ¤ and that each player has a corresponding maxmin criterion of expected utility [START_REF] Morris | Global Games: Theory and Applications[END_REF] . We allow the distributions of the signals received by the players to be different, by allowing

µ 1 6 = µ 2 .
As in Kawagoe and Ui (2010), we assume that θ is uniformally distributed on [-δ, 1 + δ] , with δ > 0; and that ε i is uniformally distributed on [-γ, γ] . [START_REF] Metz | Private and Public Information in Self-Fulfilling Currency Crises[END_REF] Because we remove the simplifying assumption that the signals received by the players may not follow the same probability distribution, we have chosen to take the mean of the probability distribution (rather than the variance) as the unknown parameter, in order to make the analysis more tractable. [START_REF] Morris | Unique Equilibrium in a Model of sel-fulfilling currency attacks[END_REF] Usually, in standard global game models of the literature, there is no bias. The mean is a priori taken equal to zero.

However, Cheli and Della Posta (2007) have argued that it might be justified to introduce biased signals in global game models. These authors underline that nothing is changed in the results if the players are aware of the bias. In our model, this is also what would happen if the bias was known (The only change would be that the switching point of the equilibrium switching strategy would be increased by the amount of the known bias, but nothing else would be changed.) Therefore, by itself, the presence of non-zero biases in the signals does not really matter in our analysis. What matters is the presence of ambiguity concerning these biases. [START_REF] Morris | Global Games: Theory and Applications[END_REF] This is a standard criterion in the literature on decision under uncertainty with ambiguity aversion (see Gilboa and Schmeidler (1989)). This was also the criterion used by Ui (2009) and Kawagoe and Ui (2010).

Note that the range £ µ, µ ¤ , which enters the maxmin criterion, reflects both the ambiguity of the available information and the aversion to ambiguity of the players (see Gadjos et al. ( 2004)).

We will assume [START_REF] Morris | Cordination and the Price od Debt[END_REF] that we have 0 < γ ≤ δ 2 ; and, to simplify the presentation [START_REF] Mukerji | An overview of economic applications of David Schmeidlers's models of decision making under uncertainty[END_REF] , it will also be assumed that we have γ ≤ [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2 .

Equilibrum

As it is usually done in such global games, we will look for equilibria in "switching strategies". When player i follows the switching strategy with switching point k, she chooses R if

x i > k and chooses N if x i ≤ k.
From the payoff structure previously given, the expected payoff of a player who chooses N (i.e. who does not roll over the loan) is equal to λ, while the expected payoff of a player who chooses R (i.e. who rolls over the loan) is equal to the probability that the investment project succeeds in that case.

Let π µ i ,µ j (k, x i ) denote the probability, conditional on having received the signal x i , that player i holds on the event that the project succeeds when the other player j follows the switching strategy with switching point k. This probability is therefore given by π µ i ,µ j (k,

x i ) = Pr µ i ,µ j [(0 ≤ θ ≤ 1 and x j > k) or (θ > 1) | x i ] .
Note that this probability depends on both parameters µ i and µ j because it depends on the probability distributions of both random variables ε i and ε j .

As underlined before, each player has some aversion to ambiguity and uses a maxmin criterion. This means that player i chooses action R if and only if we have [START_REF] Obstfeld | Models of Currency Crisiswith Self-Fulfilling Features[END_REF]

min µ i ∈ [ µ,µ ] ,µ j ∈ [ µ,µ ] π µ i ,µ j (k, x i ) > λ.

Worst case for each player

We first have the following result:

Proposition 1 We have min µ i ∈ [ µ,µ ] ,µ j ∈ [ µ,µ ] π µ i ,µ j (k, x i ) = π µ,µ (k, x i ).
This means that the worst case for player i is obtained for µ i = µ and µ j = µ. [START_REF] Morris | Cordination and the Price od Debt[END_REF] In Kawagoe and Ui (2010), the less restrictive assumption γ ≤ δ is made. This was necessary to encompass the specific parameters values they took in their experiments. Then, when they developped their theoretical analysis, they had to restrict the possible values of λ. Thus, parameter λ had to belong to the interval

£ 3 8 , 5 8 ¤ .
Here, by making the assumption γ ≤ δ 2 , our analysis can be made without further restraining λ. Any value of λ satisfying 0 < λ < 1 is allowed. [START_REF] Mukerji | An overview of economic applications of David Schmeidlers's models of decision making under uncertainty[END_REF] The possible case 1 2 < γ ≤ δ 2 , if it existed, could be taken into account without any difficulties, and would lead to the same kind of basic qualitative results. However, this would have made the analysis and the presentation of the results more cumbersome. [START_REF] Obstfeld | Models of Currency Crisiswith Self-Fulfilling Features[END_REF] As in Morris and Shin (2004), we assume that player i chooses N if she is indifferent between N and R. This assumption is actually without any consequences on the analysis and the results.

Proof: From (3) , we have θ = x iµ iε i . A larger bias µ i shifts the probability distribution that player i holds on θ, conditional on having received a signal x i , towards lower values of θ. This reduces (or at most leaves unchanged) the probability of success of the investment project through two channels. First, this may decrease the probability of being in the case θ > 1 where the project is always successful, or this may increase the probability of being in the case θ < 0 where the project is never successful. Second, as, from (3) , we have x j = θ +µ j +ε j , this reduces the probability that the other player rolls over the debt, because this decreases the probability of having x j > k. As a consequence of these two effects, player i considers that the worst case is obtained when the bias µ i of her message takes its maximum value µ. Now, consider the effect of the bias µ j of the signal received by the other player. This bias changes the probability distribution (conditional on x i ) that player i holds on the signal x j received by the other player. From (3) , we have x j = θ + µ j + ε j , and therefore a smaller bias µ j shifts this probability distribution toward lower values of x j . This implies that a smaller bias µ j decreases (or at most leaves unchanged if this probability was already equal to zero) the probability of having x j > k, and therefore decreases the probability that player j rolls over the debt. This tends to reduce the success of the investment project. Consequently, the worst case would occur when this bias would be the lowest (µ j = µ). QED According to Proposition 1, each player would act as if she believed that the bias of her own signal would be the maximum bias µ and that the bias of the signal of the other player would be the minimum bias µ.

Equilibrium switching point

Proposition 1 implies that player i (strictly) prefers action R (and therefore chooses R) if and only if we have π µ,µ (k, x i ) > λ. Let b(k) be the value of x i which makes player i indifferent between R and N, and which therefore satisfies the equality π µ,µ (k, b(k)) = λ. It can be seen [START_REF] Schmeidler | Subjective Probability and Expected Utility without Additivity[END_REF] that π µ,µ (k, x i ) is [START_REF] Schmeidler | Subjective Probability and Expected Utility without Additivity[END_REF] When we consider π µ,µ (k, x i ), we could make the same kind of analysis as what is done for π µ,µ (k, k) in the Appendix. The difference is that point E in the Figures would have coordinates (x iµ, 0) instead of (kµ, 0) . An increase in x i would then shift toward the right the support of the uniform distribution which represents the conditional distribution of the joint variable (θ, ε j ) (represented by the square ABCD in the Figures). This would increase π µ,µ (k, x i ), or possibly leave it unchanged in some cases, but it can be seen that in the case where we have 0 < π µ,µ (k, x i ) < 1 (which is satisfied in the neighborhood of k for x i because we have π µ,µ (k, k) = λ with 0 < λ < 1), this would stricly increase π µ,µ (k, x i ).

a non-decreasing function of x i , and, in the neighborhood of k, a (strictly) increasing function of x i . Consequently, if we have x i > b(k), then we have π µ,µ (k, x i ) > λ, and therefore player i chooses R; and if we have x i ≤ b(k) then we have π µ,µ (k, x i ) ≤ λ and therefore player i chooses N. This implies that the switching strategy with the switching point b(k) is the best response of player i to the switching strategy with switching point k of player j.

As a consequence, when both players use switching strategies with switching point k, where k is a solution of the equation b(k) = k, we have an equilibrium of the game. This equation can be written π µ,µ (k, k) = λ. The following proposition shows that (in general) the solution of this equation is unique, and it explicitly gives its value [START_REF] Ui | Ambiguity and Risk in Global Games[END_REF] .

Proposition 2 Let us define η ≡ 1 2 (µ -µ) (4)
1. In the case η < γ, if we have

λ 6 = 1 2 ³ 1 -η γ ´2
, there is a unique equilibrium in switching strategies, where the switching point k is such that we have

k = µ + g(η, γ, λ) (5)
where the function g(η, γ, λ) is given by:

(i) if we have 0 < λ < 1 2 ³ 1 -η γ ´2 , then we have g(η, γ, λ) = γ ⎛ ⎝ 1 -2 s µ 1 - η γ ¶ 2 -2λ ⎞ ⎠ -2η (6)
(ii) if we have

1 2 ³ 1 -η γ ´2 < λ < 1 -η γ , then we have g(η, γ, λ) = 1 -γ + 2 v u u t η 2 + γ 2 Ã 2λ - µ 1 - η γ ¶ 2 ! -2η (7)
(iii) if we have 1 -η γ ≤ λ < 1, then we have g(η, γ, λ) = 1 -γ + 2λγ (8)
(and therefore does not depend on η in this case)

In the case η < γ, if we have λ = 1 2 ³ 1 -η γ ´2 , then any switching point such that γ -2η ≤ kµ ≤ 1γ gives an equilibrium in switching strategies.

2. In the case η ≥ γ, then, for all λ (where 0 < λ < 1), there is a unique equilibrium in switching strategies, where the switching point k is given by ( 5) and (8) (and therefore kµ does not depend on η in this case).

The proof is given in the Appendix.

Effect of ambiguity on financial crises 4.1 Effect of ambiguity

Ambiguity has been defined by the couple of values ¡ µ, µ ¢ , where µ ≤ µ. We will say that

¡ µ 0 , µ 0 ¢ is more ambiguous than ¡ µ, µ ¢ if we have £ µ 0 , µ 0 ¤ ⊃ £ µ, µ
¤ , which can be written: µ 0 ≤ µ and µ 0 ≥ µ, with at least one strict inequality. Note that this implies η 0 > η, where parameter η is defined by (4) .

Let µ 1 and µ 2 be the true biases of the signals received by player 1 and player 2, respectively. Then, we will compare ¡ µ, µ ¢ to ¡ µ 0 , µ 0 ¢ , where ¡ µ 0 , µ 0 ¢ is more ambiguous than ¡ µ, µ ¢ , and where we have µ ≤ µ 1 ≤ µ, µ ≤ µ 2 ≤ µ, µ 0 ≤ µ 1 ≤ µ 0 and µ 0 ≤ µ 2 ≤ µ 0 .

A financial crisis occurs when the investment project fails because of a problem of early liquidation by creditors. This happens in the case 0 ≤ θ ≤ 1 when at least one of the two creditors does not roll over the loan. Therefore, more ambiguity increases the probability of a crisis if and only if we have k 0 > k.

From equation (5) of Proposition 2 17 , we see that ambiguity affects the switching point k, and therefore the probability of a crisis, through two channels. The first goes through the highest bias µ. The reason is that, in the worst case, we have µ i = µ, and therefore player i acts as if she believed that the bias of her signal was at its maximum value µ. As we have µ 0 ≥ µ, this makes k 0 ≥ k. 17 This equation is valid in the general case where there is a unique equilibrium. In the special case given by η < γ and λ

= 1 2 ³ 1 -η γ ´2
, where, from Proposition 2, we have a continuum of equilibria for k in the interval [µ + γ -2η, µ + 1γ] , we should add an upward jump from k to µ + 1γ in the case of more ambiguity, or a downward jump from k to µ + γ -2η in the case of less ambiguity. These additional jumps would then reinforce the effect found in the general case where there is a unique equilibrium for k.

The second channel goes through the function g(η, γ, λ), which, in cases 1-(i) and 1-(ii), depends on the ambiguity parameter η defined by (4) . In these cases, from (6) or (7) , we have ∂g(η,γ,λ) ∂η > 0, which makes k 0 > k. This second channel reinforces the effect going through the first channel and therefore contributes to making more ambiguity harmful. As more transparency is likely to reduce ambiguity, this gives a new argument in favor of transparency in such a model.

As we will see, this channel is entirely due to the fact that we have allowed µ i 6 = µ j . If, as it is done in the literature, we had assumed that the distributions of the signals of the two players were the same, and therefore that we had µ i = µ j , this channel would have disappeared and only the channel going through µ would have remained 18 . This second channel is therefore the additional channel we want to underline in our analysis, and we will now discuss it in more details in the next subsection.

The role of the perceived coordination of players

The effect of the ambiguity parameter η, which goes through g(η, γ, λ), is due to the property that, for player i, in the worst case, µ i and µ j actually differ and take the opposite extreme values (from Proposition 1 we have µ i = µ and µ j = µ in the worst case). This gap µµ, which is equal to 2η, between these values of the biases in the worst case, implies that each player acts as if she perceives that the players coordinate less. This makes each player less inclined to roll over her loan, which increases the probability of the crisis.

To better understand this effect of ambiguity on the perceived coordination of players, we can first note that, in the Bayesian analyses done in the literature, the following property holds: When player i receives a signal x i equal to the switching point k, then the other player, player j, has the same probability of rolling over the loan or of not rolling over the loan 19 . And a change in the variance of the signal does not affect this property. This same property would actually also hold in the analysis of Kawagoe and Ui (2010), and the amount of ambiguity would not alter this property. Therefore, in these analyses, whatever the amount of uncertainty is, and whatever its form (variance of the shock or ambiguity), each player (when receiving a signal equal to k) believes that, if she rolls over the debt, there is a probability 1 2 that the other player also rolls over the debt. Therefore, each player al-ways believes that the probability that there will be coordination between the actions of the two players would be equal to [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2. . In our analysis, such a property does not hold anymore. In our model, when player i receives the signal x i = k, then she acts as if she believed that the probability that the other player would roll over his loan is less than [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2 . Therefore, if player i chooses to roll over her loan, she holds the belief that the coordination of the two players will be less than [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2 . The reason of this property is the following. The probability that player j rolls over his loan is given by the probability of having x j > k. According to (3) , this is equal to the probability of having ε j > k-µ jθ. On the other hand, from (3) , the equality x i = k can be written θ = k-µ i -ε i . Therefore, replacing θ by this expression in the previous inequality, the probability of having x j > k, conditional on x i = k, is equal to the probability of having ε jε i > µ iµ j . If we had a priori assumed that we have µ i = µ j , this probability would be equal to [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2 . But, in our analysis, player i evaluates this probability by taking the worst case for µ i and µ j . Therefore player i has instead to consider the probability of having ε jε i > µµ, which can be written ε jε i > 2η. This probability is less than [START_REF] Carlsson | Global Games and Equilibrium Selection[END_REF] 2 when we have η > 0, i.e. when there is ambiguity, and this probability is a decreasing function of the ambiguity parameter η.

This effect of ambiguity, going through the perceived coordination of players, would not play a role in cases 1-(iii) and 2 of Proposition 2, where g(η, γ, λ) is given by (8) and does not depend on η. The reasons are the following. First, when the level of ambiguity η is already large enough to make the probability of having ε jε i > 2η equal to zero, which happens when we have η ≥ γ20 , then any marginal change in the value of η would be without any effect on this probability, because this probability would stay equal to zero. This corresponds to case 2 of Proposition 2. Second, when the inequality x j > k can be satisfied only for values of θ greater than 1, then the coordination of players does not matter because the investment project is always successful. When we have η < γ, this corresponds to case 1-(iii) of Proposition 221 .

Conclusion

We have considered a standard two-player global game of coordination between creditors, where creditors have to decide to roll over their loans or not, in order to finance some investment project. We have introduced some ambiguity in the model and players are assumed to have some aversion to ambiguity. We have shown that ambiguity tends to reduce the perceived coordination of players. More ambiguity leads each player to act under the belief that there is less coordination of the players. This increases the probability of a financial crisis due to early liquidation by creditors.

More precisely, suppose that a player receives a signal equal to the switching point, which makes this player indifferent between rolling over the loan or not. According to the results obtained in the existing literature which considers the same model (under a Bayesian approach but also under a non Bayesian aproach with aversion to ambiguity), this player always believes that the other player has the same probability of rolling over the loan as of not rolling over the loan. More or less uncertainty, or ambiguity, does not affect this property. Thus, if this player decides to roll over her loan, she does it under the belief that there is always a probability one half that the two players will coordinate in rolling over their loans. In our model, however, this is not what happens. Ambiguity has the effect of making this probability less than one half; and the greater ambiguity is, the smaller this probability is. If ambiguity reaches some threshold value, this probability even goes to zero.

This effect of ambiguity, going through the belief that each creditor has on the coordination of the creditors, was absent in the previous analyses done in the literature under a similar model. This occurred either because this literature used a Bayesian approach to uncertainty, or because, when it used a non-Bayesian approach with some aversion to ambiguity, it did so under the implicit assumption that the probability distributions of the signals received by the players were the same. By removing this last assumption, we have been able to show that ambiguity reduces the perceived coordination of players in rolling over their loans. This effect of ambiguity on the perceived coordination of creditors gives an additional channel through which more ambiguity tends to increase the probability of a financial crisis.

From a policy point of view, the results we obtain are in favor of more transparency. We have underlined that, by reducing ambiguity, more transparency would increase the perceived coordination between creditors. This would contribute to decreasing the probability of a crisis. Theses results imply that, in their communication to the private sector, the public authorities should try to make statements which may not be interpreted in an ambigu-ous way, and should provide information which would reduce the amount of ambiguity on the underlying fundamentals.

Note, however, that we have to be careful in interpreting these results because they may depend on the specific global game model used. Actually, the main point of our analysis is that ambiguity could change the belief that each player holds on the degree of coordination between her own action and the actions of the other players. We have shown that ambiguity could decrease this perceived coordination of players. In the model considered, which is a model of coordination between creditors who roll over their loans, the coordination of players has a beneficial role, and this is why the negative effect of ambiguity on perceived coordination is harmful.

However, the same kind of effect on perceived coordination could on the contrary make ambiguity beneficial if the coordination of players has a harmful role and can trigger a crisis. This would be the case in a global game model of currency attacks. For, in such a model, a player (speculator) is more willing to attack the currency if he believes that there is more coordination with the other players in attacking the currency. If ambiguity reduced the degree of perceived coordination of players, then more ambiguity would, on the contrary, decrease the probability of a crisis (i.e. of a currency attack). This would make ambiguity beneficial and, consequently, transparency harmful22 . These remarks suggest that it would be useful to extend the formal analysis of the present paper to a more general global game model which can encompass alternative models of financial crises.

Appendix

Proof of Proposition 1 As indicated in Section 3, the equilibrium condition is π µ,µ (k, k) = λ. By definition, and using (3) , we have

π µ,µ (k, k) = Pr µ i =µ,µ j =µ [(0 ≤ θ ≤ 1 and θ + ε j > k -µ) or (θ > 1) | x i = k].
Consider the distribution of θ conditional on having received the signal x i = k, when we have µ i = µ. From (3) , the equality x i = k can be written θ = k-µε i . Consider a value of k which belongs to the interval

£ µ -δ 2 , µ + 1 + δ 2 ¤ . As we have assumed γ ≤ δ 2 , this equality implies -δ ≤ θ ≤ 1 + δ. Consequently, for k ∈ £ µ -δ 2 , µ + 1 + δ 2 ¤
, all the possible values of θ which are compatible with having received the signal x i , belong to the support of the uniform prior on θ. This implies that the conditional distribution of θ is a uniform distribution with mean k-µ and support [kµγ, kµ + γ] . As ε j is independent of ε i , this implies that the conditional distribution of the joint variable (θ,

ε j ) is a uniform distribution having support [k -µ -γ, k -µ + γ] × [-γ, γ].
Then, we could caIculate π µ,µ (k, k) through some integration calculus, but it will be simpler, or at least more illuminating, to do it graphically. In the plane of coordinates θ and ε j , the support of the uniform conditional distribution of the joint variable (θ, ε j ) can be represented by a square ABCD centered on point E of coordinates (kµ, 0) on the horizontal axis. This is done in Figures 1, 2 and3. As we have assumed γ ≤ 1 2 , there are only three possible cases which are represented by these three figures. In Figure 1, the square ABCD is entirely in the area where we have 0 ≤ θ ≤ 1. Figure 2 corresponds to the case where the square ABCD intercepts the vertical axis, in which case we can have θ < 0 or 0 ≤ θ ≤ 1 (but never θ > 1). In figure 3, where the square ABCD intercepts the vertical line where θ = 1, we can have θ > 1 or 0 ≤ θ ≤ 1 (but never θ < 0).

The length of each side of the square ABCD is equal to 2γ. We have AB = CD = AC = BD = 2γ. In these figures we have represented the straight line (Z) of slope (-1) of equation θ + ε j = kµ. We have also drawn the straight line parallel to (Z) going through point E, which is a diagonal of the square ABCD. This diagonal would be the same as (Z) in the special case µ = µ where there would be no ambiguity.

The straight line (Z) intercepts the horizontal axis at point F, which has coordinates (x iµ, 0) and is therefore at the right of point E. We have EF = µµ = 2η. Therefore, (Z) intersects the square ABCD in two points G and H if and ony if we have η < γ.

In Figure 1, we always have 0 ≤ θ ≤ 1, which occurs when we have γ ≤ kµ ≤ 1γ. (This case is possible because we have assumed γ ≤ 1 2 ). Then, we simply have π µ,µ (k, k) = Pr µ i =µ,µ j =µ (θ +ε j > k -µ | x i = k). In the case η < γ, this probability is given by A(GBH) A(ABCD) , where A (F) represents the area of figure F. We have

A (ABCD) = AB 2 = 4γ 2 and A (GBH) = 1 2 GB 2 . As we have GB = AB -AG = AB -EF = 2 (γ -η) , we get A (GBH) = 2 (γ -η) 2 . This gives π µ,µ (k, k) = 1 2 ³ 1 -η γ ´2 .
In the case η ≥ γ, where the straight line (Z) does not intersects the square ABCD, we have π

µ,µ (k, k) = Pr µ i =µ,µ j =µ (θ + ε j > k -µ | x i = k) = 0.
The case represented in Figure 2 occurs when we have kµ < γ. In this case, the area where we have θ < 0 should be excluded in order to calculate π µ,µ (k, k). If we have η < γ, then, from Figure 2, this gives π

µ,µ (k, k) = A(GBH)-A(GP R) 4γ 2
in the case where (as in Figure 2) G is at the left of P, i.e. when we have AG < AP. We have AG = EF = 2η, and AP = SO = SE+EO = γ-(kµ) (because, in Figure 2, point E being on the left of point O, we have kµ < 0 and therefore EO = -(kµ)). Thus, the inequality AG < AP gives the condition kµ < γ -2η. As we have A (

GP R) = 1 2 GP 2 and GP = AP -AG = γ -(k -µ) -2η, this gives π µ,µ (k, k) = 1 2 ³ 1 -η γ ´2 - 1 8γ 2 [γ -(k -µ) -2η] 2 .
If G is on the right of P, which occurs when we have kµ ≥ γ -2η, then there is no relevant area where we have θ < 0, and, as in the first case, we have

π µ,µ (k, k) = 1 2 ³ 1 -η γ ´2
. Finally, as in the first case, when we have η ≥ γ, we always have π µ,µ (k, k) = 0.

In the third case, depicted in Figure 3, the square ABCD intercepts the vertical line θ = 1. This occurs when we have kµ > 1γ. Then all the area where we have θ > 1 should be included. If we have η < γ, this means that, in Figure 3, to the area of the triangle GBH, we have to add the area of LNDH. We therefore have π µ,µ (k, k) = A(GBH)+A(LHND) 4γ 2

. We can write A (LHND) = A (LIH) + A (IHND). We have A (LIH) = 1 2 IH 2 and A (IHND) = IH.HD. We have HD = EF = 2η and IH = OT -

1 = OE + ET -1 = k -µ + γ -1. Let us define ν ≡ k -µ + γ -1. we get A (LIH) = 1 2 ν 2 and A (IHND) = 2ην. This implies π µ,µ (k, k) = 1 2 ³ 1 -η γ ´2 + 1 8γ 2 (ν 2 + 4ην)
. However this calculus is valid only when G is on the left of M, as in Figure 3. This occurs when we have AG < AM. As we have AG = EF = 2η and AM = AB -IH = 2γν, this inequality can be written 2η < 2γν, or equivalently ν < 2 (γη) , which can also be written kµ < 1γ + 2 (γη) . When this inequality is not verified, i.e. when we have kµ ≥ 1γ + 2 (γη) , then G is on the right of M, and we simply have π µ,µ (k, k) = A(MBND) These results can be summarized in the following Proposition: Proposition 3 (i) In the case kµ < γ -2η, when we have η < γ, we get

π µ,µ (k, k) = 1 2 µ 1 - η γ ¶ 2 - 1 8γ 2 [γ -(k -µ) -2η] 2 (9)
and, when we have η ≥ γ, we get π µ,µ (k, k) = 0 As we have λ > 0, the equilibrium condition π µ,µ (k, k) = λ in the case η ≥ γ requires kµ > 1γ. Then, this solution is given by ν = 2λγ, which yields the solution for k given by case 2, and therefore by equations ( 5) and (8) , of Proposition 2. Note that for all possible values of λ (which satisfy 0 < λ < 1) this solution verifies the required inequality kµ > 1γ.

Finally, at the beginning of the Appendix, in order to calculate the probability distribution of θ, conditional on having x i = k, we have assumed that k belongs to the interval £ µ -δ 2 , µ + 1 + δ 2 ¤ . We therefore have to verify that the equilibrium values of k we found satisfy this requirement. This can be seen in the following way. In the extreme case k = µ -δ 2 , we would be in the case of Figure 2 where E would have coordinates ¡ -δ 2 , 0 ¢ . As we have assumed γ ≤ δ 2 , this implies that the square ABCD would be necessarily entirely contained in the region θ ≤ 0 on the left of the vertical axis. We would thus have π µ,µ (k, k) = 0 in this case. In the same way, in the other extreme case k = µ + 1 + δ 2 , we would be in the case of Figure 3 where E would have coordinates ¡ 1 + δ 2 , 0 ¢ . As we have assumed γ ≤ δ 2 , this implies that the square ABCD would be necessarily entirely contained in the region θ ≥ 1 on the right of the vertical axis θ = 1. This would give π µ,µ (k, k) = 1 in this case. But, in Figures 1, 2 and 3, an increase in k has the effect of shifting the square ABCD and the straight line (Z) to the right by the same amount. Thus, a greater k decreases the probability of having θ < 0 or increases the probability of having θ > 1 (or possibly could leave them unchanged). This implies that π µ,µ (k, k) is a non decreasing function of k (this property could also easily be seen from Proposition 3). As a consequence, because we have 0 < λ < 1, the solution of the equation π µ,µ (k, k) = λ necessarily belongs to the interval £ µ -δ 2 , µ + 1 + δ 2 ¤ . QED

4γ 2 . 2 νγ

 22 As we haveA (MBND) = IH.BD = 2νγ, this implies π µ,µ (k, k) = 1 .Finally, when we have η ≥ γ, then we also have π µ,µ (k, k) = A(MBND)

1 2 ³ 1 1 2 ³ 1 2 νγ

 1211212 η γ ´2 in the case η < γ (and to zero if η ≥ γ). Consequently, if we have λ = -η γ ´2 and η < γ, then the equilibrium condition π µ,µ (k, k) = λ can be satisfied for any value of kµ such that we have γ -2η ≤ kµ ≤ 1γ. Then, any switching point satisfying this inequality gives an equilibrium. Now consider the case η ≥ γ. Proposition 3 implies that we have π µ,µ (k, k) = 0 if we have kµ ≤ 1γ, and π µ,µ (k, k) = 1 if we have kµ > 1γ.

  Figure 1

See Diamond and Dybvig ((1983) and[START_REF] Obstfeld | Models of Currency Crisiswith Self-Fulfilling Features[END_REF] for such analyses.

See Carlson, H. and E. van Damme (1993) and, for a survey on global games, see[START_REF] Morris | Global Games: Theory and Applications[END_REF] .

See for example[START_REF] Metz | Private and Public Information in Self-Fulfilling Currency Crises[END_REF].

Two classical references are[START_REF] Gilboa | Maximin Expected Utility with Non-Unique Prior[END_REF] and[START_REF] Schmeidler | Subjective Probability and Expected Utility without Additivity[END_REF]. In these non-Bayesian frameworks, the presence of some aversion to ambiguity leads the decision maker to give more weight to the bad outcomes implied by each decision.

On the application of such a non Bayesian approach to various issues, and on how this approach may help explain some existing empirical puzzles, see for example[START_REF] Mukerji | An overview of economic applications of David Schmeidlers's models of decision making under uncertainty[END_REF].

As explained in[START_REF] Ui | Ambiguity and Risk in Global Games[END_REF], the reason for having these different effects of ambiguity is the following. More ambiguity makes players more willing to choose the action with a payoff which does not depend on the unknown state of fundamentals. In the bank runs model, and in the model of coordination of creditors to roll over their loans, this action helps the crisis to occur. It respectively consists in withdrawing the deposits (and then getting cash), or in not rolling over the debt (and then getting the known value of the collateral). On the contrary, in the currency attacks model, it is the action which consists in not attacking the currency, i.e. in not participating to the creation of the crisis, which

[START_REF] Ui | Ambiguity and Risk in Global Games[END_REF] introduces the same kind of ambiguity in a more general global game with a continuum of players.

In that case, although each player would be almost certain about the value θ of the fundamentals, there would remain a non negligible uncertainty on higher orders beliefs. This is sufficient to produce a unique equilibrium. See[START_REF] Morris | Global Games: Theory and Applications[END_REF] for a review of these kinds of models.

Following the same kind of argument as in[START_REF] Morris | Global Games: Theory and Applications[END_REF], it could be shown that the switching strategy with switching point k, where k is a solution of the equation b(k) = k, survives the iterated deletion of interim-dominated strategies. And, when there is a unique solution to this equation, the corresponding switching strategy is the unique strategy which survives the iterated deletion of interim-dominated strategies.

If we had imposed µ i = µ j , we can easily see that the worst case would have been obtained for µ i = µ j = µ. Therefore, ambiguity would have had an effect only through µ, as in the first channel.

Such a property has been emphasized in the literature (see for example[START_REF] Morris | Global Games: Theory and Applications[END_REF]).

When we have η ≥ γ, the values of ε jε i satisfying the inequality ε jε i > 2η would be outside the support of ε jε i .

This can easily be seen in the following way. From (3) and µ j = µ, the inequality x j > k can be written θ > kµ -ε j . Using (5) and (8) , this inequality becomes θ > 1 + 2η + (2λ -1) γε j . Consequently, this inequality will be satisfied only for values of θ greater than 1 if and only if we have 2η + (2λ -1) γε j ≥ 0. This is verified for all ε j if and only if it is verified for ε j = γ. Then, as we have 2η + (2λ -1) γε j = 0 for ε j = γ and λ = 1 -η γ , the inequality is satisfied if and only if we have λ ≥ 1 -η γ , which gives the inequalities for λ of case 1-(iii) of Proposition 2.

As indicated in the Introduction, the model of speculative attacks is also a model where, even without the effect on the perceived coordination of players that we underline in the present paper, the existing literature (Ui (2009)) has shown that more ambiguity has a favorable effect on crises. Thus, in this model too, the effect of ambiguity going through the perceived coordination of players would contribute to reinforcing the effect of ambiguity that was shown to be present in the existing literature. When we switch from the coordination of creditors model to the the currency attacks model, both effects would change signs. Therefore, it seems that the effect on perceived coordination underlined in our analysis makes the effect of ambiguity on financial crises stronger, whatever its sign is. Therefore, the respective implications on the either beneficial or harmful effects of transparency would also become stronger.

(ii) In the case γ -2η ≤ kµ ≤ 1γ, when we have η < γ, we get

and, when we have η ≥ γ, we get π µ,µ (k, k) = 0 (iii) In the case η < γ and

where we have defined

(iv) In the case kµ ≥ 1γ + 2 (γη) if we have η < γ, and in the case kµ > 1γ if we have η ≥ γ we get

The equilibrium condition is π µ,µ (k, k) = λ. First, consider the case η < γ . Then, if we look for a solution satisfying the inequality kµ < γ -2η of case (i) of Proposition 2. In the case η < d, using (9) , π µ,µ (k, k) = λ gives a second order equation in the variable (kµ). It can easily be shown that this equation has solutions if and only if we have 0 < λ < 1 2 ³

1 -η γ ´2 ; and, when this last inequality is satisfied, there is a unique solution satisfying the inequality kµ < γ -2η, and this is the solution given by (5) and (6) of Proposition 2.

In the same way, we can look for a solution satisfying 1γ < kµ < 1γ + 2 (γη) of case (iii) of Proposition 3. Using (12) , this inequality can be written 0 < ν < 2 (γη) . Using (11) , π µ,µ (k, k) = λ gives a second order equation in ν which is

It can easily be shown that this equation has a solution satisfying the inequalities

, and this solution is then unique and is given by ( 5) and (7) of Proposition 2.

When we look for a solution satisfying inequality k -µ ≥ 1-γ +2 (γη) of case (iv) of Proposition 3, using (13) , we get ν = 2λγ; using (12) , this gives the solution for k given by (5) and (8) of Proposition 2. This solution satisfies the corresponding inequality kµ ≥ 1 + γ -2η, if and only if we have λ ≥ 1 -η γ . The case (ii) of Proposition 3, where we look for a solution satisfying γ -2η ≤ kµ ≤ 1γ is peculiar because π µ,µ (k, k) is always equal to


Member, IEEE Claudio Weidmann
email: claudio.weidmann@ieee.org

Member, IEEE Gottfried Lechner
email: gottfried.lechner@unisa.edu.au

A Fresh Look at Coding for q-ary Symmetric Channels

Keywords: q-ary symmetric channel, low-density paritycheck (LDPC) codes, decoder front-end

This paper studies coding schemes for the q-ary symmetric channel based on binary low-density parity-check (LDPC) codes that work for any alphabet size q = 2 m , m ∈ N, thus complementing some recently proposed packetbased schemes requiring large q. First, theoretical optimality of a simple layered scheme is shown, then a practical coding scheme based on a simple modification of standard binary LDPC decoding is proposed. The decoder is derived from first principles and using a factor-graph representation of a front-end that maps q-ary symbols to groups of m bits connected to a binary code. The front-end can be processed with a complexity that is linear in m = log 2 q. An extrinsic information transfer chart analysis is carried out and used for code optimization. Finally, it is shown how the same decoder structure can also be applied to a larger class of q-ary channels.

I. INTRODUCTION

T HE q-ary symmetric channel (q-SC) with error probabil- ity ǫ takes a q-ary symbol at its input and outputs either the unchanged input symbol, with probability 1 -ǫ, or one of the other q -1 symbols, with probability ǫ/(q -1). It has attracted some attention recently as a more general channel model for packet-based error correction. For very large q, its appropriately normalized capacity approaches that of an erasure (packet loss) channel. In the following, we will only consider channel alphabets of size q = 2 m with m ∈ N.

The capacity of the q-SC with error probability ǫ is

C q-SC = m -h(ǫ) -ǫ log 2 (2 m -1)
bits per channel use, where h(x) = -x log 2 x-(1-x) log 2 (1x) is the binary entropy function. Asymptotically in m, the normalized capacity C q-SC /m thus approaches 1-ǫ, which is the capacity of the binary erasure channel (BEC) with erasure probability ǫ.

Recent work [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF]- [START_REF] Zhang | Analysis of verification-based decoding on the q-ary symmetric channel for large q[END_REF] has shown that it is possible to devise coding schemes that approach C q-SC for large alphabet sizes q = 2 m , with symbols of hundreds to thousands of bits, and complexity O(log q) per code symbol. The focus of the present work is on smaller q, with symbols of tens of bits at most, although the presented coding techniques will work for any q = 2 m .

The q-ary channel input and output symbols will be represented by binary vectors of length m. Hence a simplistic coding approach consists in decomposing the q-SC into m binary symmetric channels (BSCs) with crossover probability

ǫ BSC = qǫ 2(q -1) = ǫ 2(1 -2 -m ) , (1)
which have capacity C BSC = 1 -h(ǫ BSC ) each.

We briefly study the normalized capacity loss, ∆ = C q-SC /m -C BSC , which results from (wrongly) assuming that the q-SC is composed of independent BSCs. For fixed m, we have lim ǫ→0 ∆ = 0; so using binary codes with independent decoders on the m-fold BSC decomposition might be good enough for small ǫ (e.g. ǫ < 10 -3 ). However, Fig. 1 shows that the relative capacity loss m∆/C q-SC = 1 -mC BSC /C q-SC increases close to linearly in ǫ. For fixed ǫ, we have lim m→∞ ∆ = h(ǫ/2) -ǫ, which can be a substantial fraction of the normalized q-SC capacity (e.g., for ǫ = 0.1, h(ǫ/2) -ǫ = 0.19). Fig. 2 shows that already for small m, the q-SC capacity is substantially larger than what can be achieved with the BSC decomposition. Clearly, there is a need for coding schemes targeted at "large" ǫ (say ǫ > 10 -1 ), but moderate m (say 2 ≤ m < 20), which are not that well handled by methods for large q. For example, to use verification-based decoding, the symbols should have between m = 32 bits for short codes (block length 10 2 . . . 10 3 ) and m = 64 bits for longer codes (block length 10 4 . . . 10 5 ) [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF].

One example application, which also motivated this work, is Slepian-Wolf coding of q-ary sources with a discrete impulsenoise correlation model, using q-SC channel code syndromes as fixed-rate (block) source code. This can then be used as a building block for a Wyner-Ziv coding scheme, where q is the number of scalar quantizer levels, or for fixed-rate quantization of sparse signals with a Bernoulli-ǫ prior on being nonzero [START_REF] Weidmann | Practical distributed source coding with impulse-noise degraded side information at the decoder[END_REF]. Clearly, q will be only moderately large in such a scenario.

The capacity loss of the binary decomposition is due to the fact that the correlation between errors on the binary sub-channels is not taken into account, i.e., since an error on one sub-channel of the q-SC implies a symbol error, the error probabilities on the other sub-channels will change

ε m = log 2 q 1-m C BSC / C q-SC Fig. 1. Relative capacity loss 1 -mC BSC C q-SC
of marginal BSC vs. q-SC. conditioned on this event. A better approach would be the use of non-binary low-density parity-check (LDPC) codes over GF(q) [START_REF] Davey | Low density parity check codes over GF(q)[END_REF]. While that would take into account the dependency between bit errors within a symbol, the decoding complexity of the associated non-binary LDPC decoder is O(q • log q) or at least O(q) when using sub-optimal algorithms [START_REF] Declercq | Decoding algorithms for nonbinary LDPC codes over GF(q)[END_REF].

Instead, this work focuses on a modified binary LDPC decoder of complexity O(log q). Section II studies an ideal scheme using layers of different-rate binary codes, providing the key intuition that once a bit error is detected, the remaining bits of the symbol may be treated as erasures without loss in rate. Section III-A then proposes a scheme using a single binary code and develops the new variable node decoding rules from first principles, by factorizing the posterior probabilities. Section III-B shows that the new decoding rule is equivalent to a front-end (or first receiver block) that maps q-ary symbols to groups of m bits and studies its factor graph representation. Section III-C analyzes the extrinsic information transfer chart characterization of this q-SC front-end, which is shown to allow capacity-achieving iterative decoders. Section IV briefly outlines how to design optimized LDPC codes for this problem and presents simulation results. Finally, Section V extends these decoding methods to a larger class of q-ary channels.

II. LAYERED CODING SCHEME

We study the following layered coding scheme based on binary codes. Blocks of k symbols

[u 1 , u 2 , . . . , u k ] are split into m bit layers [u 1 i , u 2 i , . . . , u k i ], i = 1, . . . , m,
and each layer is independently encoded with a code for a binary symmetric erasure channel (BSEC) with erasure probability δ i and crossover probability ǫ i , to be specified below. The channel input symbol will be denoted x j = [x j 1 , x j 2 , . . . , x j m ] T , where x j i is the i-th bit of the j-th symbol, while the corresponding channel output is y j = [y j 1 , y j 2 , . . . , y j m ] T , respectively y j i . The key idea is to decode the layers in a fixed order and to declare bit erasures at those symbol positions in which a bit error occurred in a previously decoded layer. This saves on the code redundancy needed in the later layers, since erasures can be corrected with less redundancy than bit errors.

It will be shown that this layered scheme is optimal if the constituent BSEC codes attain capacity. The intuition behind the optimality of this seemingly suboptimal scheme is that once a bit error (and thus a symbol error) has been detected, all the following layers have bit error probability 1/2 in that position, since the q-SC assigns uniform probabilities over the possible symbol error values. Now the BSC(1/2) has zero capacity and so the concerned bits can be treated as erasures with no loss.

The decoder performs successive decoding of the m layers, starting from layer 1. All errors corrected at layer i and below are forwarded to layer i + 1 as erasures, that is all bit error positions found in layers 1 up to i will be marked as erased in layer i + 1, even though the channel provides a (possibly correct) binary output for those positions. Let ǫ i be the probability that the channel output y is equal to the input x in bit positions 1 to i -1 and differs in position i (i.e. [y 1 , y 2 , . . . , y i-1 ] T = [x 1 , x 2 , . . . , x i-1 ] T and y i = x i ). A simple counting argument shows that there are 2 m-i such binary vectors y = x, out of a total 2 m -1. The i-th binary sub-channel is thus characterized by

ǫ i = 2 m-i 2 m -1 ǫ, (2)
δ i = i-1 j=1 ǫ j = 2 m -2 m-i+1 2 m -1 ǫ. (3)
Theorem 1 The layered scheme achieves q-SC capacity if the constituent BSEC codes achieve capacity.

Proof: We may assume an ideal scheme, in which all layers operate at their respective BSEC capacities and correct all errors and erasures. The BSEC(δ i , ǫ i ) capacity is

C BSEC = (1 -δ i ) 1 -h ǫ i 1 -δ i . ( 4
)
Hence the sum of the layer rates becomes

m i=1 R i = m i=1 (1 -δ i ) 1 -h ǫ i 1 -δ i (5) = m + m i=1 -δ i -(1 -δ i ) log 2 (1 -δ i ) + ǫ i log 2 ǫ i + (1 -δ i+1 ) log 2 (1 -δ i+1 ) (6)
= m + m i=1 -(m -i)ǫ i + ǫ i log 2 ǫ i + (1 -p) log 2 (1 -p) (7)
= m + m i=1 -(m -i)ǫ i + (m -i)ǫ i + p log 2 p -p log 2 (2 m -1) + (1 -p) log 2 (1 -p) (8) = m -h(p) -p log 2 (2 m -1) = C q-SC ,
where (5) follows from (4) and the definition of the layered scheme, (6) follows from δ i + ǫ i = δ i+1 (which holds up to i = m, when δ m+1 = ǫ), [START_REF] Davey | Low density parity check codes over GF(q)[END_REF] follows from the evaluation of the telescoping sum and [START_REF] Declercq | Decoding algorithms for nonbinary LDPC codes over GF(q)[END_REF] follows from substituting (2) for ǫ i .

m i=1 δ i = m i=1 (m -i)ǫ i , and
As can be seen from inserting (2) and ( 3) into (4), the layer rate quickly approaches 1 -ǫ for increasing i, that is, for large m the last layers all operate at rates close to 1 -ǫ. Thus an interesting variant of the layered scheme is to use µ < m BSEC layers as above, followed by a single "thicker" layer, which sends the remaining m-µ bits (per symbol) over the same BSEC(δ µ+1 , ǫ µ+1 ). In particular, this could even be beneficial in practical implementations, since combining layers leads to longer codewords and thus better codes, which might outweigh the theoretical rate loss. The next section will show that it is actually possible to reap the benefits of a single large binary code, without any layering, by using a decoder that exploits the dependencies among the bits in a symbol.

The layered scheme has several disadvantages compared to the symmetric scheme presented below. The main disadvantage is that in practical implementations, each layer will need a different BSEC code that is tuned to the effective erasure and error probabilities resulting from the layers preceding it. Besides causing problems with error propagation, this is also impractical for hardware implementation, since the required silicon area would necessarily grow with the number of layers. Another disadvantage is that for a fixed symbol block length n, the layered scheme uses binary codes of length n, while the symmetric scheme uses block length mn. The latter will provide a performance advantage, especially for short block lengths.

III. BIT-SYMMETRIC CODING SCHEME

Ideally, a coding scheme for the q-SC should be symmetric in the bits composing a symbol, that is, no artificial hierarchy among bit layers should be introduced (notice that the order of the bit layers may be chosen arbitrarily). We propose to encode all bits composing the symbols with one "big" binary code, which needs to satisfy just slightly stricter constraints than an ordinary code, while the decoder alone will exploit the knowledge about the underlying q-SC. The key concept that should carry over from the layered scheme is that the decoder is able to declare erasures at certain symbol positions and thus needs less error correction capability (for part of the bits in erased symbols).

We present two approaches to describe the decoder for the proposed scheme: a bit-level APP approach, which clearly displays the probabilities being estimated (and is more intuitive to generalize, see Sec. V), and a decoder front-end approach, which facilitates the use of EXIT chart tools. The model underlying both approaches is the same: the decoder will use estimates of the extrinsic symbol error probabilities to estimate the marginal bit error probabilities, thus "adjusting" the individual error probabilities of the binary sub-channels.

A. Bit-Level APP Approach

Our proposal for a practical symmetric q-SC coding scheme relies on an LDPC code with information block length K = mk bits and channel block length N = mn bits. We assume that the variable nodes (VNs) in the decoder receive independent extrinsic soft estimates of X j i (that is, bit i of code symbol/vector X j , for i = 1, . . . , m, j = 1, . . . , n) from the check nodes (CNs). These amount to estimates of P (X j i |Y [j] = y [j] ) or the corresponding log-likelihood ratio (LLR), L(X) = log(Pr(X = 0)/ Pr(X = 1)). (As usual, the notation y [j] denotes the block consisting of all symbols/vectors except the j-th.) In particular, the extrinsic estimate of X j i is assumed to be independent of the other bits X j

[i] of the same symbol, so that we may write

P (X j i |X j 1 , . . . , X j i-1 , Y [j] = y [j] ) = P (X j i |Y [j] = y [j]
).

In the standard case, these independence assumptions are justified by the fact that asymptotically in the block length, the neighborhood of a VN in the LDPC decoder computation graph becomes a tree [START_REF] Richardson | Modern Coding Theory[END_REF]Chap. 3]. Unfortunately, the q-SC VN message computation rule has to depend on the other bits in the same symbol, in order to account for the bit error correlation, and thus will introduce cycles. However, this problem can be alleviated by imposing an additional constraint on the code, namely that the parity checks containing X j i do not involve any of the bits X j

[i]
. This is a necessary condition for the above intra-symbol independence assumption and may be achieved by using an appropriate edge interleaver in the LDPC construction. Then the cycles introduced by the VN message rule will grow asymptotically and are thus not expected to lead to problems in practice.

As suggested above, the properties of the q-SC can be taken into account via a simple modification of the VN computation in the message-passing decoding algorithm for binary LDPC codes. We factor the a posteriori probability (APP) of symbol X j as follows:

P (X j |Y = y) . = P (Y j = y j |X j )P (X j |Y [j] = y [j] ) = P (Y j = y j |X j ) m i=1 P (X j i |Y [j] = y [j] ), (9)
where the factorization in ( 9) is made possible by the above independence assumption (the symbol . = denotes equality up to a positive normalization constant). Using the definition of the q-SC, this becomes

P (X j = x j |Y = y) . = (1 -ǫ) m i=1 P (X j i = x j i |Y [j] = y [j] ), x j = y j , ǫ q-1 m i=1 P (X j i = x j i |Y [j] = y [j] ), x j = y j . ( 10
)
We define the extrinsic probability that X j = y j as

β j = m i=1 P (X j i = y j i |Y [j] = y [j] ) = m i=1 p j i ,
where we introduced

p j i = P (X j i = y j i |Y [j] = y [j] ) (11)
for notational convenience. The normalization constant in [START_REF] Brink | Design of low-density parity-check codes for modulation and detection[END_REF] thus becomes

γ j = (1 -ǫ)β j + ǫ q -1 (1 -β j ).
Then the bit APP may be obtained by the marginalization

P (X j i = x j i |Y = y) = x j [i] ∈{0,1} m-1 P (X j = x j |Y = y), (12)
which may be written as

P (X j i = x j i |Y = y) =    (1 -ǫ)β j [i] + ǫ q-1 (1 -β j [i] ) • p j i γ j , x j i = y j i , ǫ q-1 • 1-p j i γ j , x j i = y j i , (13)
where β j

[i] = β j /p j i is the intra-symbol extrinsic probability that X j = y j , using no information on bit X j i . Finally, we may express the a posteriori bit-level LLR as

L app (X j i = y j i ) = log (q -1)β j -qǫβ j + ǫp j i ǫ(1 -p j i ) = log (q -1)β j [i] -qǫβ j [i] + ǫ ǫ • p j i 1 -p j i = log 1 + q -qǫ -1 ǫ • β j [i] L ch (X j i = y j i ) +L extr (X j i = y j i ). (14)
The usual L(X) is obtained from L(X = y) = log(Pr(X = y)/ Pr(X = 1 -y)) via a sign flip, L(X) = (1 -2y)L(X = y).

The second term in [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF] corresponds to the extrinsic information from the CNs that is processed at the VNs in order to compute the bit APP in standard binary LDPC decoding. The difference lies in the first term in [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF], which corresponds to the channel LLR (which would be L ch (X) = log(P (y|X = 0)/P (y|X = 1)) in the binary case). When the extrinsic information on the bits X j

[i] favors the hypothesis X j = y j , the product β j

[i] will be small and therefore L ch in ( 14) will be close to zero, which is equivalent to declaring a bit erasure. This shows that the symmetric LDPC scheme relies on "distributed" soft bit erasure estimates, while in the layered scheme the erasures are declared in a hard "top-down" fashion.

Equation ( 14) describes the modification of the VN computation that turns a message-passing binary LDPC decoder into one for the q-ary symmetric channel. The outgoing VN messages are computed as usual by subtracting the incoming edge message from L app (X j i ); also the CN messages are the same as in the binary case. For practical implementation purposes, [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF] should probably be modified (approximated) in order to avoid switching back and forth between probabilities and LLRs when computing β j .

A final detail is the specification of the initial channel LLR L (0) ch in [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF], which is needed to start the decoder iterations. By inserting the memoryless worst-case estimate β j

[i] = 2 -m+1 into ( 14), we obtain

L (0) ch = log 2(1 -2 -m ) -ǫ ǫ , (15)
which is exactly the channel LLR for the marginal BSC with crossover probability ǫ BSC given in [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF]. Notice that the decoder iterations are exclusively between VN [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF] and CN computations, like in the binary case. However, computing [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF] at the VNs requires the extrinsic information (the CN messages) for all bits within a symbol; this might be considered an additional level of message exchanges (specifically, plain copying of messages), but it does not involve iterations of any kind. The complexity increase compared to binary LDPC decoding is on the order of at most m operations per variable node, depending on the scheduling. In fact, the marginalization ( 12) is reminiscent of a combined detector and VN decoder for binary LDPC codes that are directly mapped to larger signal constellations [START_REF] Brink | Design of low-density parity-check codes for modulation and detection[END_REF]. Thanks to the symmetry of the q-SC, here it is not necessary to actually sum over all q symbol values.

B. q-SC Front-end Approach

The similarity of the bit-APP approach to combined detection and decoding mentioned above points to a different view on the bit-symmetric coding scheme, which is to consider a q-SC front-end for a binary LDPC decoder, similar to approaches for iterative demapping and decoding [START_REF] Sanderovich | LDPC coded MIMO multiple access with iterative joint decoding[END_REF], [START_REF] Lechner | Optimization of LDPC codes for receiver frontends[END_REF]. These techniques involve proper iterations between the demapper and the LDPC decoder, being treated as separate functional blocks.

The q-SC front-end takes into account the correlation between the errors on the m bit layers. Its factor graph representation allows to formulate a message passing algorithm that computes essentially the same quantities as the approach in Sec. III-A, but opens the way to EXIT analysis and displays more clearly the opportunity for further complexity reduction by appropriate message scheduling.

As before, let x denote the vector of q-ary channel input symbols x j (j = 1, . . . , n) and let x j i denote bit i of symbol j. In the same way, the output of the channel is represented by y, y j and y j i , and the errors are denoted by e, e j and e j i , respectively. We assume w.l.o.g. that e j i = x j i ⊕ y j i , where ⊕ denotes addition in GF [START_REF] Brown | Probabilistic decoding of interleaved RS-codes on the q-ary symmetric channel[END_REF], and e j = x j ⊕ y j , by extension.

f ch f ch f E m µ e 1 →f E (e1) µ f E →e 1 (e1) µ f ch →e 1 (e1) µ e 1 →f ch (e1) µ x 1 →f ch (x1) µ f ch →x 1 (x1)
Fig. 3. Factor graph representation of the q-SC front-end for symbol x j (the symbol index j is omitted).

Let χ C (x) be the characteristic function of the code, which evaluates to one if x is a codeword and to zero otherwise. Furthermore assuming that the transmitted codewords are equally likely, the a posteriori probability satisfies the proportionality relation

f X|Y (x|y) . = χ C (x)f Y|X (y|x).
The q-ary channel is assumed to be memoryless (on the symbol level), leading to a factorization of f Y|X as

f X|Y (x|y) . = χ C (x) n j=1 f Y |X (y j |x j ) = χ C (x) n j=1 f Y,E|X (y j , x j ⊕ y j |x j ),
where we used the fact that x j , e j and y j are related in a deterministic way. Given an error symbol e j , the bit-layers are independent of each other, leading to

f X|Y (x|y) . = χ C (x) n j=1 f E (e j )f Y |X,E (y j |x j , e j ) = χ C (x) n j=1 f E (e j ) m i=1 f j ch (y j i |x j i , e j i )
,

where f j ch = f Y j i |X j i ,E j i
. This factorization is shown for one symbol x j in Fig. 3, where the edges on the right side are connected to the check nodes of the LDPC code, i.e. the factorization of the characteristic function χ C (x). In the following, we will denote a message sent from a variable node x to a function node f and vice versa as µ x→f (x) and µ f →x (x), respectively [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF].

1) Message Passing Rules: We apply the sum-product algorithm to compute the marginals f X j i |Y (x j i |y) for all symbols j and all bits i, i.e. to perform a posteriori decoding for every bit of the transmitted codeword. In the following we will describe the operations for a single q-ary symbol and therefore omit the symbol index j for convenience.

First, we define the local functions and derive the message passing rules for the function nodes f ch and f E . Since the variable nodes e i have degree two, they just forward the incoming messages, e.g. µ e1→fch (e 1 ) = µ fE →e1 (e 1 ) and µ e1→fE (e 1 ) = µ fch→e1 (e 1 ).

a) Bit Layer Channels: In the binary sub-channels, x i , y i and e i have to sum up to zero in GF(2), therefore the local functions f ch are given by

f ch (y i |x i , e i ) = [y i = x i ⊕ e i ],
where [P ] evaluates to 1 if the expression P is true and to 0 otherwise.

Having defined the local function, we can derive the message passing algorithm by applying the rules of the sumproduct algorithm. Given a message µ xi→fch (x i ) and a received bit y i , the channel function node computes

µ fch→ei (e i ) = ∼{ei} f ch (y i |x i , e i ) • µ xi→fch (x i ) = µ xi→fch (e i ⊕ y i ),
where ∼{a} denotes the marginalization over all variables except a. In the same way, the message sent back to variable node x i is computed as

µ fch→xi (x i ) = ∼{xi} f ch (y i |x i , e i ) • µ ei→fch (e i ) = µ ei→fch (x i ⊕ y i ).
b) Error Patterns: The function node f E represents the probability that a certain binary error pattern occurs. In the q-ary symmetric channel, every error pattern has the same probability ǫ q-1 , except the all-zero pattern that has probability 1 -ǫ, thus

f E (e 1 , . . . , e m ) = 1 -ǫ, if e 1 = . . . = e m = 0 ǫ q-1 , otherwise.
The derivation of the outgoing messages of f E leads to

µ fE →ei (e i ) = ∼{ei} f E (e 1 , . . . , e m ) • i ′ =i µ e i ′ →fE (e i ′ ) = (1 -p) • β [i] + ǫ q-1 1 -β [i] if e i = 0 ǫ q-1 if e i = 1,
where β [i] is defined as

β [i] = i ′ =i µ e i ′ →fE (0). ( 16
)
Appendix A outlines the simplification of the different messages using scalar quantities and highlights the fact that these are essentially the same quantities as in the bit-level APP approach in Sec. III-A.

2) Complexity: Clearly, the processing complexity of the front-end is dominated by [START_REF] Hu | Regular and irregular progressive edge-growth Tanner graphs[END_REF] and is thus O(log q) per symbol, as in verification decoding [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF]. This means that the overall decoding complexity scales linearly in the number of transmitted bits, independently of the symbol alphabet size q. Complexity may be further reduced by a constant factor (i.e. not its order) if the front-end messages are not recomputed on every LDPC decoder iteration; this is often sufficient in practice.

C. EXIT Analysis of the q-SC Front-end

In this section, we analyze the q-SC front-end using extrinsic information transfer (EXIT) charts [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF], which will also be used later for the design (optimization) of LDPC codes.

Let the a priori and extrinsic messages for the front-end denote the messages between the bit layer sub-channels f ch and the bit nodes x i of the LDPC code, that is, µ xi→fch (x i ) and µ fch→xi (x i ), respectively. For the EXIT chart analysis, the front-end is characterized by the transfer function I e (I a ), where I a and I e denote the a priori and the extrinsic mutual information, respectively, between the messages and the corresponding bits.

First, we derive the EXIT function of the front-end for the case when the a priori messages are modeled as coming from a binary erasure channel (BEC). In this special case, the EXIT functions have important properties (e.g. the area-property), which were shown in [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF].

In the case of a BEC, the variables x i are either known to be error-free or erased, thus simplifying the computation of β [i] defined in [START_REF] Hu | Regular and irregular progressive edge-growth Tanner graphs[END_REF] as follows. The product in [START_REF] Hu | Regular and irregular progressive edge-growth Tanner graphs[END_REF] has m -1 factors, taking on the value 1/2 if the bit x i is erased, 0 if the bit x i is not in agreement with the received bit y i and 1 otherwise. If at least one message is not in agreement with the received bit, a symbol error occurred and

β [i] = 0. Otherwise, β [i] = 2 -t
, where t denotes the number of erased messages.

Since β [i] = 0 corresponds to ǫ i = 1/2 through (22) in Appendix A, this case is equivalently described by an erasure. Therefore, the extrinsic messages can be modeled as being transmitted over a binary symmetric erasure channel (BSEC), with parameters ǫ m-t and δ m-t given by ( 2) and (3), respectively, since t erasures correspond to the situation in layer i = m -t in the layered scheme of Section II. Its capacity is thus

I t = (1 -δ m-t ) 1 -h ǫ m-t 1 -δ m-t . (17)
In order to compute the extrinsic information I e (I a ) at the output of the front-end as

I e (I a ) = m-1 t=0 I t λ t (I a ), (18)
we have to compute the probability λ t (I a ) that t messages are erased given a priori mutual information I a . Let ∆ a = 1 -I a denote the probability that an a priori message is erased. The probability that t = 0, . . . , m -1 out of m -1 messages are erased is computed as

λ t (I a ) = m -1 t ∆ t a (1 -∆ a ) m-1-t = m -1 t (1 -I a ) t I m-1-t a . (19)
The EXIT function for BEC a priori messages can therefore be computed using (2), ( 3), ( 17) and ( 19) in (18).

Theorem 2 An iterative decoder for the bit-symmetric scheme using a q-SC front-end can attain q-SC capacity.

Proof: According to the area theorem for EXIT charts [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF], the capacity of each bit layer is given by the area below the EXIT function, if the a priori messages are modeled as coming from a BEC. Therefore, the capacity of the overall channel is given by

C tot = m 1 0 m-1 t=0 I t λ t (I a ) dI a = m m-1 t=0 I t 1 0 λ t (I a ) dI a = m m-1 t=0 I t m -1 t 1 0 (1 -I a ) t I m-1-t a dI a = m m-1 t=0 I t (m -1)! (m -1 -t)!t! t!(m -1 -t)! m! = m-1 t=0 I t = C q-SC , (20)
where we used the fact that the integral corresponds to the definition of the beta function. The last sum in (20) is indeed equal to the capacity of the q-SC, as was already shown in the proof of Theorem 1. Without iterative processing, the maximum achievable rate is given by I e (0). In that case, all a priori messages are erased and one has

I m-1 = 1 -h (ǫ 1 ) = 1 -h qǫ 2(q -1) = C BSC ,
which corresponds to the simplistic coding approach where the q-SC is decomposed into m BSCs. Fig. 4 shows an EXIT chart for BEC a priori messages. If the q-SC would be decomposed into BSCs (without iterating between the front-end and the LDPC code and without using the layered scheme) then the value at I a = 0 corresponds to the capacity of these BSCs. In contrast, the area below the EXIT functions corresponds to the normalized capacity of the q-SC.

When using this front-end with an LDPC code, the a priori messages can not be modeled as coming from a BEC. For code design, we will make the approximation that the messages are Gaussian distributed, which is a common assumption when using EXIT charts. The simulated EXIT function using Gaussian a priori messages is also shown in Fig. 4.

IV. LDPC DESIGN AND CONSTRUCTION

After obtaining the EXIT function of the q-SC front-end, we can design an LDPC code. Code design is an optimization problem that selects the degree distributions of the code in order to maximize the rate, under the constraint that the EXIT function of the overall LDPC code does not intersect the EXIT function of the q-SC front-end.

Joint optimization of the variable and check node degree distributions is a nonlinear problem, but it was shown in [START_REF] Lechner | Optimization of LDPC codes for receiver frontends[END_REF] that the optimization of the check node degree distribution given a fixed variable node degree distribution is a linear programming problem, which can be solved efficiently.

To reduce the optimization complexity and to obtain practical degree distributions, we choose three non-zero variable node degrees (compare e.g., the approach in [START_REF] Brink | Design of repeat-accumulate codes for iterative detection and decoding[END_REF]). This allows to perform an exhaustive search over the variable node degree distribution, and for each variable node degree distribution we optimize the check node degree distribution as described in [START_REF] Lechner | Optimization of LDPC codes for receiver frontends[END_REF] with a maximum check node degree d c,max = 50.

Fig. 5 shows the normalized capacity of the q-SC and the obtained optimized code rates (under the Gaussian approximation) versus the error probability ǫ of the q-SC for m = 4 and m = 8. Using this code optimization, we are able to design codes that perform close to capacity over a wide range of error probabilities for moderate q.

For the actual code construction, we used a modified version of the PEG algorithm [START_REF] Hu | Regular and irregular progressive edge-growth Tanner graphs[END_REF], [START_REF] Hu | Software for PEG code construction[END_REF], which allows us to construct codes with a specific variable and check node degree distribution. To avoid (short) cycles in the overall factor graph, one has to ensure that the bits of a given q-ary symbol do not participate in the same parity check. This can be achieved by using an appropriate interleaver between the q-SC frontend and the LDPC decoder. Another way would be to use the multi-edge type framework for LDPC code where such constraints can be explicitly specified [START_REF] Richardson | Modern Coding Theory[END_REF]Chap. 7].

To verify our derivations, we performed bit error rate simulations for an optimized binary LDPC code of rate R = 1/2 and length N = 12000, shown in Fig. 6. This code is optimized for a q-SC with m = 4, thus N = 12000 bits correspond to k = 1500 q-ary symbols. It has a decoding threshold of ǫ = 0.28 (the Shannon limit for R = 1/2 is at ǫ = 0.29). As a comparison we also show the bit error rate for a regular LDPC code with d v = 3 and d c = 6 which has a decoding threshold of ǫ = 0.25.

V. GENERALIZATION TO CONDITIONALLY INDEPENDENT BINARY SUB-CHANNELS

The decoder in Section III is seen to easily extend to q-ary channels with modulo-additive noise, where the m bits of the noise (error pattern) are independent if an error occurs, i.e. if

L app (X j i = y j i ) = log   (1 -ǫ)β j + α(1 -ǫ i| * )p j i k =i ǫ k| * + p j k -2ǫ k| * p j k -k =i (1 -ǫ k| * )p j k αǫ i| * (1 -p j i ) k =i ǫ k| * + p j k -2ǫ k| * p j k   = log   (1 -α)β j [i] + α(1 -ǫ i| * ) k =i ǫ k| * + p j k -2ǫ k| * p j k αǫ i| * k =i ǫ k| * + p j k -2ǫ k| * p j k   + log p j i 1 -p j i = log   1 -ǫ i| * ǫ i| * + (1 -α)β j [i] αǫ i| * k =i ǫ k| * + p j k -2ǫ k| * p j k   L ch (X j i = y j i ) +L extr (X j i = y j i ). (21)
at least one bit is nonzero. This assumption leads to define the q-ary symmetric channel with conditionally independent binary sub-channels (q-SC*), with transition probabilities

P Y |X (y|x) = 1 -ǫ, y = x, α m i=1 ǫ xi⊕yi i| * 1 -ǫ i| * 1⊕xi⊕yi , y = x,
where α = ǫ 1 -m i=1 1 -ǫ i| * and ⊕ denotes GF(2) addition (this definition encompasses all channels satisfying the above conditional independence assumption, from which it may be derived axiomatically). The defining parameters are the symbol error probability ǫ and the m conditional probabilities ǫ i| * , which are the bit error probabilities conditioned on the event that at least one of the other m-1 bits is in error. The marginal bit error probabilities will be ǫ BSC,i = αǫ i| * . Since the q-SC* is strongly symmetric, the uniform input distribution achieves its capacity

C q-SC* = m -α m i=1 h(ǫ i| * ) + (1 -ǫ) log 2 (1 -ǫ) + α log 2 α -(α -ǫ) log 2 (α -ǫ).
When ǫ is such that α = 1, the q-SC* reduces to m independent BSCs, while for ǫ i| * = 1 2 , i = 1, . . . , m, it becomes an ordinary q-SC.

The unnormalized bit APP (compare (13)) is obtained as x j i = y j i , αǫ i| * (1 -p j i ) k =i ǫ k| * + p j k -2ǫ k| * p j k , x j i = y j i , leading to the LLR expression (21). The quantities p j i , β j and β j

P (X j i = x j i |Y = y) . =                 
[i] are as defined in Section III. Like in the special case of the q-SC, for β j

[i] → 0 the channel LLR L ch tends to a constant, which is equal to the LLR of the binary sub-channel conditioned on the occurrence of an error on one or more of the other sub-channels. The initial value of L ch can again be obtained by assuming a worst-case of p j k = 1 2 , β j [i] = 2 -m+1 in (21), yielding

L (0) ch (X j i = y j i ) = log 1 -ǫ i| * ǫ i| * + 1 -α αǫ i| * = log 1 -αǫ i| * αǫ i| * = log 1 -ǫ BSC,i ǫ BSC,i ,
which is the channel LLR of the i-th marginal BSC.

APPENDIX A. Simplification of the Messages

Since all involved variables are binary, we can represent the messages by scalar quantities. For the messages from and to the variable nodes x j i of the LDPC code, we use log-likelihood ratios of the corresponding messages L a,i = log µ xi→fch (0) µ xi→fch (1) , L ch,i = log µ fch→xi (0) µ fch→xi [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF] .

The connection with the bit-level APP approach is made by equating µ xi→fch (b) = P (X j i = b|Y [j] = y [j] ) in the expression for L a,i ; the correspondence for L ch,i will be given below.

The messages from the function nodes f ch to the node f E are defined as the probability of no error p i = µ fch→ei (0) = µ ei→fE (0), and the messages from the function node f E are defined as the error probability ǫ i = µ fE →ei (1) µ fE →ei (0) + µ fE →ei [START_REF] Luby | Verification-based decoding for packet-based low-density parity-check codes[END_REF] .

Using these definitions, we can reformulate the computation rules at the function nodes as

p i = e L a,i 2 •(1-2yi) e L a,i 2
+ e -L a,i 2 , which corresponds to [START_REF] Sanderovich | LDPC coded MIMO multiple access with iterative joint decoding[END_REF], and

ǫ i = ǫ q-1 (1 -ǫ) • β [i] + ǫ q-1 1 -β [i] + ǫ q-1 = ǫ 2ǫ + β [i] (q -ǫq -1) (22)
For the initialization, we set all a-priori L-values L a,i to zero, leading to β [i] = 2 -(m-1) = 2/q. Inserting this in (22) leads to ǫ i = ǫq 2(q -1) = ǫ BSC .

Finally, the messages sent from the function nodes f ch to the variable nodes x i are computed as

L ch,i = (1 -2y i ) • log 1 -ǫ i ǫ i . (23)
Using ( 22), the logarithmic term in (23) can be expanded as

log 1 -ǫ i ǫ i = log 2 + q -qǫ -1 ǫ • β [i] -1 ,
which is equivalent to L ch (X j i = y j i ) defined in [START_REF] Ashikhmin | Extrinsic information transfer functions: Model and erasure channel properties[END_REF] in the bit-level APP approach.

Fig. 2 .

 2 Fig.2. Normalized capacity of q-SC vs. marginal BSC (error probability ǫ = 0.1).

Fig. 4 .

 4 Fig.[START_REF] Shokrollahi | Capacity-approaching codes on the q-ary symmetric channel for large q[END_REF]. EXIT function for the q-SC front-end with BEC (analytical) and Gaussian (simulated) a priori messages for ǫ = 0.25, m = 4 (lower curves) and m = 8 (upper curves).

Fig. 5 .Fig. 6 .

 56 Fig. 5. Rate of optimized codes versus normalized capacity of the q-SC for m = 4 and m = 8.

( 1 -ǫ) m k=1 p j k +α( 1 -

 11 ǫ i| * )p j i k =i ǫ k| * + p j k -2ǫ k| * p j k k =i (1 -ǫ k| * )p j k ,

ACKNOWLEDGMENTS

The authors would like to thank Jossy Sayir for helpful discussions and for pointing out the similarity with iterative demapping and decoding.

This work has been supported by the Australian Research Council under ARC grant DP0881160.