CALTECH Charles R Plott

Jean-Louis Rullière

Marie Claire Villeval

Introduction to the special issue Special issue on Behavioral Public Economics

The workshop of the Association for Public Economic Theory on behavioral and experimental public economics held in Lyon in 2009 attracted a large audience of public economists interested in exploring the behavioral foundations of individual and collective decision-making in the context of public economics. By allowing the possibility of testing theoretical models, experimental methods have significantly increased our understanding of major issues in public economics such as the relative efficiency of various institutions supporting the provision of public goods and cooperation, mechanism design for public policies or voting systems. This special issue demonstrates how lively and diversified the ongoing experimental research in public economics has come to be. Among the numerous submissions to this issue, we have selected eight papers that illustrate various facets of behavioral public economics. The contributions to this special issue focus on three main sets of questions: what are the power and the limitations of voting and legal enforcement systems, especially in terms of enhanced cooperation? Can one improve the provision of public goods by allowing sequential contributions, a mix of sanctions and rewards, or multiple punishment stages? Can speculation be used as a collusion-breaking device in auctions and is the potential hypothetical bias in valuation tasks without incentives originating in the preference elicitation method or in the preference formation?

The first set of papers investigates the interactions between legal and social sanctions and the power and limitations of voting systems. Legal norm enforcement is in many cases and ineffective deterrent due to relatively low risks of detection, On the other hand, a significant body of experimental evidence has been collected in the last decade suggesting both the importance of decentralized sanctions and the disciplining effect of these social sanctions on individuals' behavior in situations where the society faces a social dilemma. In such an environment, people have the opportunity to punish their group members based on their level of cooperation, i.e. their contribution to a public good. Usually, centralized and decentralized sanctioning institutions are studied in isolation although they coexist in most real settings. Therefore, it is difficult to assess their relative influence on human behavior and to compare their efficiency ceteris paribus. The first paper of this issue by Sebastian Kube and Christian Traxler offers a fascinating experimental analysis of the relationships between legal and social norm enforcement, in examining whether these institutions are complements or substitutes. Their experimental design allows them to measure to which extent the existence of a legal enforcement institution affects the individuals' willingness to implement decentralized sanctions to their group members. The baseline treatment consists of a standard public good game without any legal rule but in which group members can sanction their group members at a cost to themselves. A second treatment introduces a legal enforcement institution that sanctions any detected deviation from the optimal contribution to a public good after players have decided on exerting their right to sanction group members. The design is also original in that the strategy method is used to elicit the players' willingness to condition their sanctioning behavior on various possible triples of contributions of their group members. Interestingly, Kube and Traxler find that the introduction of a legal institution crowds-out the social norm enforcement without eliminating it. Their experiment also reveals that a higher level of cooperation is achieved when the legal institution complements the decentralized enforcement institution. This evidence in favor of combining legal and social sanctions deserves all the more attention as a higher cooperation is achieved at a lower overall cost.

In the first paper, sanctions resulted either from the law or from an individual choice. But one can find many intermediate situations in which a community decides on the regime that governs if and how deviations from a social norm are punished. If the members of these communities share the same social preferences and similar productive characteristics, an agreement should not be very hard to reach. The situation is much more complex when heterogeneity is present. Charles N. Noussair and Fangfang Tan also examine the effect of sanctions on contributions in a public goods game. However, they introduce an environment in which individuals have the opportunity to vote on the implementation of the punishment institution in their group. Therefore, it is not only the enforcement of sanctions that is endogenous, but also the institution itself. A novelty of their experimental design lies in the fact that the players' type is determined by two possible returns from the public goods. Group members vote on whether the sanctioning institution should target the individuals who contributed more than the average of the group or those who contributed less than the average, conditional on their type. The results confirm that heterogeneity reduces the likelihood of reaching a consensus for implementing the most efficient sanctioning institution that targets the individuals who contribute below the average unconditional on their productivity type. Most groups end up with a regime without punishment because individuals vote defensively to avoid to be punished by targeting the other group members' type.

A voting procedure does not necessarily allow individuals to implement more efficient rules, but its very existence may also affect individual behavior after the vote has taken place. This hypothesis could hold not only in the domain of public good provision, but also in the political arena. In particular, one might wonder whether and how the existence of a voting procedure and its modalities condition the behavior of individuals once elected. There is surprisingly little empirical evidence in economics on this issue. Hong Geng, Arne Robert Weiss and Irenaeus Wolff address the question of how the nature of political campaigns can prevent the risk that an elected leader takes full selfish advantage of his position. They have designed an experiment in which one electoral campaign is based on the description of the candidates' personality while another campaign is based on the candidates' explicit promises on future actions if elected. The elected candidate then becomes the decider in a following dictator game with three recipients and his behavior can be compared with that of randomly selected leaders in a control treatment. Surprisingly, experiments with both German and Chinese subjects show that dictators tend to behave more pro-socially in the absence of elections than after campaigns in which no promises are announced. This striking result indicates that personality-based campaigns may reduce the social distance between the elected leader and his voters but may also increase the elected candidate's feeling of entitlement. Another interesting result the authors find is that the existence of promises-based campaign leads to higher dictators' transfers, which cannot be interpreted as being a consequence of an inflation of promises resulting from the electoral competition. This study reveals that the combination of competition, cheap talk, and guilt-aversion increases the power of elections to limit the opportunistic use of power but not as much as theoretically predicted. This study should have interest beyond public economists, especially in political science.

The second set of papers in this special issue aim at contributing to the experimental literature on the design of mechanisms influencing cooperation in situations involving social dilemmas. Various institutions have been considered such as allowing the individuals to communicate before making their decisions, introducing a leader in order to influence the rest of the group through his example or his sacrifice, permitting individuals to punish or to exclude free-riders, or introducing voluntary mobility across groups. Most of these institutions have been shown to improve cooperation but their contribution to social welfare is not straightforward. The three following studies contribute to this analysis.

In most sequential public goods experiments, the selection of leaders is either random or based on past behavior or intrinsic characteristics. Authors have mainly considered leadership by example. There are many instances, however, in which individuals self-select as first movers and this may result in detrimental consequences. [START_REF] Varian | Sequential contributions to public goods[END_REF] proposed a model in which individuals can decide to move first and thereby commit to free-ride in order to signal to the other players that they will have to contribute more to provide the public goods. Thus, the opportunity to commit first may aggravate the free-riding problem. Daniele Nosenzo and Martin Sefton embed Varian's model in two extended endogenous timing games with either observable delay or action commitment. In the first game, there are two contribution stages and players commit to contribute in the first or the second stage before choosing their actual contribution. In the second game, each player decides on either contributing or waiting. The theoretical predictions are derived for both standard selfish preferences and for inequality averse preferences. Nosanzo and Sefton test the predictions of these games by means of a clever experiment in which the players can choose the timing of their contribution and commit to contribute only once. Interestingly, the results show that most participants avoid committing in the first stage of both extended games contrary to the predictions of the game with observable delay. This demonstrates that the opportunity to commit does not automatically aggravate the free-riding problem. However, when a player with a high value of the public good commits to contribute first, then the total amount of the public good is decreased.

Reprisals in case of deviations from social norms are frequently observed in the laboratory even though they do not belong to the equilibrium of the game. A criticism pointed out initially by [START_REF] Houser | When punishment fails: Research on sanctions, intentions and non-cooperation[END_REF] is that sanctions may be detrimental to efficiency in the short run because they destroy resources. The use of rewards instead of sanctions may avoid this difficulty. Nathalie Colombier, David Masclet, Daniel Mirza, and Claude Montmarquette provide an original study in which they compare the impact of rewards and sanctions on international cooperation. Indeed, if one interprets voluntary contributions to public goods as an individual decision, it might be also relevant to use this game to investigate international cooperation in the presence of social dilemmas. One can think of environmental issues but there are many other examples. Colombier et al. consider cooperation in counterterrorism in which international security is treated as a public good. This constitutes a very stimulating approach. In their experiment, each country is faced with three possible uses of its resources. It may invest in an international collective action reducing the expected losses from a terrorist attack. Alternatively, it may invest in its own national security, entailing a displacement of the terrorists' targets towards less insured countries. Finally, it can invest in other activities that are not related to security. The results demonstrate that the players prefer investing in their own security than in collective action. On the other hand, the introduction of endogenous sanctions and rewards increases cooperation. While the use of reprisals reduce efficiency, as stated by [START_REF] Houser | When punishment fails: Research on sanctions, intentions and non-cooperation[END_REF], rewards generate positive effects on welfare and they are much more frequently used by players than sanctions, probably because they expect some reciprocity from other players. These very neat findings support the idea that more effective counterterrorism require some institutional coordination.

Andreas Nicklisch and Irenaeus Wolff propose that endogenous punishment in social dilemma situations may be driven more by deviations from an absolute norm than by deviations from a relative norm that fluctuates with the average contribution in the group. This distinction has important implication for the predictive power of theories of pro-social behavior for sanctions in public good games. To address this, Nicklisch and Wolff have designed a public good experiment with multi-stage punishment including a finite but endogenous number of stages. After the group members have decided on their contribution levels to the public account, they can announce whether and to which group members they want to assign punishment points; next, they decide on the punishment they actually implement. The steps of announcements and sanctions can be repeated until players are no longer willing to sanction others. The results show no evidence of counter-punishment in iterated stages of punishment. Instead, they tend to support the influence of an absolute cooperation norm that corresponds to the contribution of the full endowment.

The issue ends with two contributions related to auctions. One paper examines speculation as a collusion breaking device and the other studies the hypothetical bias in the elicitation of preferences with second price auctions. Florence Naegelen, Michel Mougeot, Benjamin Pelloux, and Jean-Louis Rullière analyze auction mechanisms for allocating CO2 emission permits in the laboratory taking into account the concern for a possible collusion between bidders. They test experimentally the hypothesis that the presence of speculators may break collusion in this market by means of a 2x2 design. In their experiment, two auction mechanisms are introduced: sealed bid auctions with uniform price and ascending clock auctions. In one treatment, high emitters and low emitters participate in the auction and speculation is ruled out, while in the other, a third category of players called non-emitters, is introduced who can not themselves use permits, but can speculate in the market. A spot market for trades opens after the auctions take place. As predicted, the experimental results show that the presence of speculators results in higher auction prices and higher revenues for the sellers in the sealed bid auctions with uniform prices, This may be because the compliance agents tend to adopt outbidding strategies. The impact of speculators is weaker in the ascending clock auctions and prices are lower than under the other auction mechanism. Overall, however, the presence of speculators reduces efficiency under both mechanisms by impeding the allocation of permits to the producers with the highest values.

Finally, the issue closes with a paper that takes a more methodological perspective. Indeed, behavior in auctions may differ according whether choices entail actual monetary consequences or only hypothetical ones. This phenomenon is known as the hypothetical bias which could originate either in the preference elicitation method or in the preference formation. Nicolas Jacquemet, Robert-Vincent Joule, Stéphane Luchini, and Jason F. Shogren investigate the origin of the discrepancy between values elicited with or without monetary incentives by comparing bids in the two treatments of two experiments using the same Vickrey auction procedures. In one experiment, they use induced values to study preference elicitation, while in the second, they elicit homegrown values to identify preference formation regarding a real non-market good (the protection of dolphins). According to the treatment, the choices do or do not have monetary implications. Interestingly, Jacquemet et al. do not find any evidence of a hypothetical bias when using induced values whereas they observe a substantial hypothetical bias when eliciting homegrown values with much higher bids in the hypothetical than in the incentivized treatment. These findings tend to support to the role of preference formation in driving the discrepancy of valuations with and without monetary incentives. Another lesson is that it is especially important to commit individuals not to violate their budget constraint when one intends to reveal demand for non-market goods properly.

In conclusion, we hope that this special issue will contribute to and encourage the development of behavioral and experimental public economics. This is not only because the following contributions provide fascinating new evidence on public economics issues, but also because they should lead to enriched theoretical models by incorporating these new empirical findings regarding human motivation.

Plan of the special issue Special issue on Behavioral


Marco Di Renzo
email: marco.direnzo@lss.supelec.fr

Dario De Leonardis

Fabio Graziosi
email: fabio.graziosi@univaq.it

Harald Haas
email: h.haas@ed.ac.uk

On the Performance of Space Shift Keying (SSK) Modulation with Imperfect Channel Knowledge

In this paper, we study the sensitivity and robustness of Space Shift Keying (SSK) modulation to imperfect channel knowledge at the receiver. Unlike the common widespread belief, we show that SSK modulation is more robust to imperfect channel knowledge than other state-of-the-art transmission technologies, and only few training pilots are needed to get reliable enough channel estimates for data detection. More precisely, we focus our attention on the so-called Time-Orthogonal-Signal-Design (TOSD-) SSK modulation scheme, which is an improved version of SSK modulation offering transmit-diversity gains, and provide the following contributions: i) we develop a closedform analytical framework to compute the Average Bit Error Probability (ABEP) of a mismatched detector for TOSD-SSK modulation, which can be used for arbitrary transmit-antenna, receive-antenna, channel fading, and training pilots; ii) we perform a comparative study of the performance of TOSD-SSK modulation and the Alamouti code under the same imperfect channel knowledge, and show that TOSD-SSK modulation is more robust to channel estimation errors; iii) we point out that only few pilot pulses are required to get performance very close to the perfect channel knowledge lower-bound; and iv) we verify that transmit-and receive-diversity gains of TOSD-SSK modulation are preserved even for a mismatched receiver.

I. INTRODUCTION

Space modulation is a novel digital modulation concept for Multiple-Input-Multiple-Output (MIMO) wireless systems, which is receiving a growing attention due to the possibility of realizing low-complexity and spectrally-efficient MIMO implementations [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF]- [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]. The space modulation principle is known in the literature in different forms, such as Information-Guided Channel Hopping (IGCH) [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF], Spatial Modulation (SM) [START_REF] Mesleh | Spatial modulation[END_REF], and Space Shift Keying (SSK) modulation [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. Although different from one another, all these transmission technologies share the same fundamental working principle, which makes them different from conventional modulation schemes: they encode part of the information bits into the spatial position of the antenna-array, which plays the role of a constellation diagram (the so-called "spatial-constellation diagram") for data modulation [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]. In particular, SSK modulation exploits only the spatial-constellation diagram for data modulation, which results in a very low-complexity modulation concept for MIMO systems [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. Recently, we have introduced in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], [START_REF] Di Renzo | Space shift keying (SSK-) MIMO over correlated Rician fading channels: Performance analysis and a new method for transmitdiversity[END_REF] and generalized in [START_REF] Di Renzo | Space shift keying (SSK) modulation: On the transmitdiversity/multiplexing trade-off[END_REF], respectively, an improved version of SSK modulation, which can achieve transmit-diversity gains without any spectral efficiency loss with respect to the original SSK modulation proposal.

In SSK modulation, blocks of information bits are mapped into the index of a single transmit-antenna, which is switched on for data transmission while all the other antennas radiate no power [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. Regardless of the information message to be transmitted, and, thus, the active transmit-antenna, SSK modulation exploits the location-specific property of the wireless channel for data modulation [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]: the messages sent by the transmitter can be decoded at the destination since the receiver sees a different channel impulse response on any transmit-toreceive wireless link. In [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF] and [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF], it has been shown that the achievable performance of SSK modulation depends on how different the channel impulse responses are. In other words, the channel impulse responses are the points of the spatialconstellation diagram, and the receiver performance depends on the distance among these points. Recent results have shown that SSK modulation can provide better performance than conventional modulation schemes with similar complexity if the receiver has Perfect Channel State Information (P-CSI) [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF]- [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. However, due to its inherent working principle, the major criticism about the application of SSK modulation in a realistic propagation environment is the robustness of the space modulation principle to the imperfect knowledge, at the receiver, of the wireless channel. In particular, since the wireless channel is the actual modulation unit, it is often argued that the space modulation concept is more sensitive to channel estimation errors. The main contribution of this paper is to shed light on this matter.

Although some research works on the performance of the space modulation principle with imperfect channel knowledge are available in the literature, these results are insufficient and only based on numerical simulations. In [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF], the authors study the Average Bit Error Probability (ABEP) of SSK modulation with non-ideal channel knowledge. However, there are four limitations in this paper: i) the ABEP is obtained only through Monte Carlo simulations, which is not very much insightful; ii) the arguments in [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF] are applicable only to Gaussian fading channels and do not take into account the cross-product between channel estimation error and Additive White Gaussian Noise (AWGN) at the receiver; iii) it is unclear from [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF] how the ABEP changes with respect to the pilot symbols used by the channel estimator; and iv) the robustness/weakness of SSK modulation with respect to conventional modulation schemes is not analyzed. In [START_REF] Di Renzo | Space shift keying (SSK) modulation with partial channel state information: Optimal detector and performance analysis over fading channels[END_REF], we have studied the performance of SSK modulation when the receiver does not exploit the knowledge of the phase of the channel gains for data detection (semi-blind receiver). The main message of this paper is that semi-blind receivers are much worse than coherent detection schemes, and, thus, that the assessment of the performance of coherent detection with imperfect channel knowledge is a crucial aspect for SSK modulation. A very interesting study has been recently conducted in [START_REF] Ulla Faiz | Recursive least-squares adaptive channel estimation for spatial modulation systems[END_REF], where the authors have compared the performance of SM and V-BLAST (Vertical Bell Laboratories Layered Space-Time) [START_REF] Wolniansky | V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel[END_REF] schemes with practical channel estimates. It is shown that the claimed sensitivity of space modulation to channel estimation errors is simply a misconception and that, on the contrary, SM is more robust than V-BLAST to imperfections on the channel estimates, and that less training is, in general, required by SM. However, the system in [START_REF] Ulla Faiz | Recursive least-squares adaptive channel estimation for spatial modulation systems[END_REF] is studied only through Monte Carlo simulations, which does not give too much insights for performance analysis and system optimization.

Motivated by these considerations, in this paper we aim at developing a very general analytical framework to assess the performance of the space modulation concept with coherent detection and practical channel estimates. Our theoretical and numerical results corroborate the findings in [START_REF] Ulla Faiz | Recursive least-squares adaptive channel estimation for spatial modulation systems[END_REF], and highlight two important outcomes: 1) space modulation can be even more robust to channel estimation errors than conventional modulation schemes, and 2) the number of pilot symbols required to approach the lower-bound set by coherent detection with perfect channel knowledge is quite limited. More precisely, the contributions of this paper are as follows: i) we develop a general analytical framework to compute the ABEP of the TOSD-SSK modulation scheme with imperfect channel knowledge. The framework can handle arbitrary transmit-antenna, receive-antenna, fading channel statistics, and number of pilot symbols used by the channel estimation unit. It is shown that the mismatched detector of TOSD-SSK modulation [START_REF] Taricco | Space-time decoding with imperfect channel estimation[END_REF] can be cast in terms of a quadratic-form in complex Gaussian Random Variables (RVs) when conditioning upon fading channel statistics, and that the ABEP can be computed by exploiting the Gil-Pelaez inversion theorem [START_REF] Renzo | On the cumulative distribution function of quadratic-form receivers over generalized fading channels with tone interference[END_REF]; ii) we compare the performance of TOSD-SSK modulation with the Alamouti scheme [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF], which similar to TOSD-SSK modulation can achieve transmit-diversity equal to two, and show that TOSD-SSK modulation is more robust to imperfect channel knowledge; and iii) we show that transmitand receive-diversity of TOSD-SSK modulation with nonideal channel estimates is always preserved.

The reminder of this paper is organized as follows. In Section II, the system model is introduced and the TOSD-SSK modulation scheme is briefly described. In Section III, the analytical framework to compute the ABEP with imperfect channel knowledge is developed. In Section IV, numerical results are shown to substantiate the main findings of the paper. Finally, Section V concludes the paper.

II. SYSTEM MODEL

We consider a generic N t × N r MIMO system, with N t and N r being the number of transmit-and receive-antenna, respectively. TOSD-SSK modulation works as follows [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF], [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF]- [START_REF] Di Renzo | Space shift keying (SSK) modulation: On the transmitdiversity/multiplexing trade-off[END_REF]: i) the transmitter encodes blocks of log 2 (N t ) data bits into the index of a single transmit-antenna, which is switched on for data transmission while all the other antennas are kept silent, and ii) the receiver solves a N t -hypothesis detection problem to estimate the transmit-antenna that is not idle, which results in the estimation of the unique sequence of bits emitted by the encoder. With respect to conventional SSK modulation [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF], in TOSD-SSK modulation the i-th transmitantenna, when active, radiates a distinct pulse waveform w i (•) for i = 1, 2, . . . , N t , and the waveforms across the antennas are time-orthogonal, i.e. 1 ,

+∞ -∞ w i (t) w * j (t) dt = 0 if i = j and +∞ -∞ w i (t) w * j (t) dt = 1 if i = j.
We emphasize here that in TOSD-SSK modulation a single antenna is active for data transmission and that the transmitted message is still encoded into the index of the transmit-antenna and not into the impulse response of the shaping filter. In other words, the proposed concept is different from conventional Single-Input-Single-Output (SISO) schemes, which use Orthogonal Pulse Shape Modulation (O-PSM) [START_REF] Ney Da Silva | Spectrally efficient UWB pulse shaping with application in orthogonal PSM[END_REF] and are unable to achieve transmit-diversity, as only a single wireless link is exploited for communication [START_REF] Di Renzo | Space shift keying (SSK-) MIMO over correlated Rician fading channels: Performance analysis and a new method for transmitdiversity[END_REF], [START_REF] Di Renzo | Space shift keying (SSK) modulation: On the transmitdiversity/multiplexing trade-off[END_REF]. Also, the TOSD-SSK modulation principle is different from conventional transmitdiversity schemes [START_REF] Derryberry | Transmit diversity in 3G CDMA systems[END_REF]. Further details are available in [START_REF] Di Renzo | Space shift keying (SSK-) MIMO over correlated Rician fading channels: Performance analysis and a new method for transmitdiversity[END_REF] and [START_REF] Di Renzo | Space shift keying (SSK) modulation: On the transmitdiversity/multiplexing trade-off[END_REF], which are here omitted in order to avoid repetitions. In [START_REF] Di Renzo | Space shift keying (SSK-) MIMO over correlated Rician fading channels: Performance analysis and a new method for transmitdiversity[END_REF], [START_REF] Di Renzo | Space shift keying (SSK) modulation: On the transmitdiversity/multiplexing trade-off[END_REF], it is shown that the diversity gain of the TOSD-SSK modulation scheme is 2N r , which results in a transmitdiversity equal to two and a receive-diversity equal to N r .

In this paper, the block of bits encoded into the index of the i-th transmit-antenna is called "message" and is denoted by m i for i = 1, 2, . . . , N t . The N t messages are equiprobable. Moreover, the related transmitted signal is denoted by s i (•). It is implicitly assumed in this notation that, if m i is transmitted, the analog signal s i (•) is emitted by the i-th transmit-antenna while the other antennas radiate no power.

A. Notation

The main notation used in this paper is as follows. i) We adopt a complex-envelope signal representation. ii

) j = √ -1 is the imaginary unit. iii) (x ⊗ y) (t) = +∞ -∞ x (ξ) y (t -ξ) dξ is the convolution of signals x (•) and y (•). iv) |•| 2 is the square absolute value. v) E {•} is the expectation operator. vi)
Re {•} and Im {•} are the real and imaginary part operators, respectively. vii)

Pr {•} denotes probability. viii) Q (x) = 1 √ 2π +∞ x
exp -t 2 2 dt is the Q-function. ix) m denotes the message estimated at the receiver. x) E m is the average energy transmitted by each antenna that emits a nonzero signal. xi) T m denotes the signaling interval for each information message m i (i = 1, 2, . . . , N t ). xii) The noise η l at the input of the l-th receive-antenna (l = 1, 2, . . . , N r ) is a complex AWGN process, with power spectral density N 0 per dimension. Across the receive-antenna, the noises η l are statistically independent. xiii) E p and N p denote the energy transmitted for each pilot symbol and the number of pilot symbols used for channel estimation. xiv) δ (•) and δ •,• are the Dirac and Kronecker delta functions, respectively. xv) For ease of notation, we set γ=E m /N 0 and r pm = E p /E m . xvi) M X (s) = E {exp (sX)} and Ψ X (ν) = E {exp (jνX)} denote Moment Generating Function (MGF) and Characteristic Function (CF) of RV X, respectively.

B. Channel Model

We consider a general frequency-flat slowly-varying channel model with generically correlated and non-identically distributed fading gains. In particular (i = 1, 2, . . . , N t , l = 1, 2, . . . , N r ):

• h i,l (t) = α i,l δ (t -τ i,l
) is the channel impulse response of the transmit-to-receive wireless link from the i-th transmit-antenna to the l-th receive-antenna. α i,l = β i,l exp (jϕ i,l ) is the complex channel gain with β i,l and ϕ i,l denoting the channel envelope and phase, respectively, and τ i,l is the propagation time-delay. • The delays τ i,l are assumed to be known at the receiver, i.e., perfect time-synchronization is considered. Furthermore, we assume τ 1,1 ∼ = τ 1,2 ∼ = . . . ∼ = τ Nt,Nr , which is a realistic assumption when the distance between the transmitter and the receiver is much larger than the spacing between transmit-and receive-antennas [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]. Due to the these assumptions, the propagation delays can be neglected in the reminder of this paper.

C. Channel Estimation

Similar to [START_REF] Proakis | Probabilities of error for adaptive reception of M-phase signals[END_REF] and [START_REF] Gifford | Diversity with practical channel estimation[END_REF], we assume that channel estimation is performed by using a Maximum-Likelihood (ML) detector and by observing N p pilot pulses that are transmitted before the modulated data. During the transmission of one block of pilot-plus-data symbols, the wireless channel is assumed to be constant, i.e., a block-fading channel is considered. With these assumptions, the estimates of the channel gains α i,l (i = 1, 2, . . . , N t , l = 1, 2, . . . , N r ) can be written as follows:

αi,l = βi,l exp j φi,l = α i,l + ε i,l (1)
where αi,l , βi,l , and φi,l are the estimates of α i,l , β i,l , and ϕ i,l , respectively, at the output of the channel estimation unit, and ε i,l is the additive channel estimation error, which can be shown to be complex Gaussian distributed with zero mean and variance σ2 ε = N 0 /(E p N p ) per dimension [START_REF] Proakis | Probabilities of error for adaptive reception of M-phase signals[END_REF], [START_REF] Gifford | Diversity with practical channel estimation[END_REF]. The channel estimation errors ε i,l are statistically independent and identically distributed, as well as statistically independent of the channel gains and the AWGN at the receiver.

D. Mismatched ML-Optimum Detector

In this paper, for data detection we consider the so-called mismatched ML-optimum receiver according to the definition given in [START_REF] Taricco | Space-time decoding with imperfect channel estimation[END_REF]. In particular, a detector with mismatched metric estimates the complex channel gains as in [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF] and uses the result in the same metric that would be applied if the channel were perfectly known. This detector can be obtained as follows.

Let m n with n = 1, 2, . . . , N t be the transmitted message 2 . The signal received after propagation through the wireless fading channel and impinging upon the l-th receive-antenna can be written as follows:

r l (t) = sn,l (t) + η l (t) if mn is sent (2)
where sn,l (t where Di is the mismatched decision metric:

) = (s n ⊗ h n,l ) (t) = α n,l s n (t) = β n,l exp (jϕ n,l ) s n (t) for n = 1,
Di = Nr l=1 Re Tm r l (t) ŝ * i,l (t) dt - 1 2 Tm ŝi,l (t) ŝ * i,l (t) dt (4)
and ŝi,l (t) = αi,l s i (t) = (α i,l + ε i,l ) s i (t) for i = 1, 2, . . . , N t and l = 1, 2, . . . , N r . If the transmitted message is m n , which results in switching on the n-th transmitantenna for data transmission, the detector will be successful in detecting the transmitted message, i.e., m = m n , if and only if max i=1,2,...,Nt Di = Dn .

By using (2), the decision metric in (4), when conditioning upon the transmission of message m n , i.e., D i|mn , can be written as follows (n = 1, 2, . . . , N t , i = 1, 2, . . . , N t ):

D i|mn = Nr l=1 Re α n,l α * i,l Emδ i,n + α * i,l Em ηi,l - Em 2 Nr l=1 αi,l 2 (5)
with ηi,l = Tm η l (t) w * i (t) dt.

III. PERFORMANCE ANALYSIS

In this section, we summarize the main steps to compute the ABEP of the mismatched detector in (3). To this end, we exploit the same methodology proposed in [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF] for a receiver with P-CSI, but generalize the derivation to account for channel estimation errors. More specifically, the ABEP can be tightly upper-bounded as follows [4, Eq. ( 34)]:

ABEP ≤ 1 2 (Nt -1) N t t 1 =1 N t t 2 =t 1 =1 APEP (TXt 1 → TXt 2 ) (6)
where APEP (TX t1 → TX t2 ) denotes the Average 3 Pairwise Error Probability (APEP) of the transmit-antenna TX t1 and TX t2 with t 1 , t 2 = 1, 2, . . . , N t , i.e., the probability of detecting TX t2 when, instead, TX t1 is actually transmitting. More specifically, APEP (TX t1 → TX t2 ) is the ABEP of an equivalent 2 × N r MIMO system where only the transmitantenna TX t1 and TX t2 can be switched on for transmission. In this section, exact closed-form expressions of the APEPs in (6) are given.

A. Computation of PEPs

Let us start by computing the PEPs, i.e., the pairwise probabilities in (6) when conditioning upon fading channel statistics. From (3), the PEP (TX t1 → TX t2 ) is as follows:

PEP (TXt 1 → TXt 2 ) = Pr D t 1 |m t 1 < D t 2 |m t 1 (7)
where, from (5), D t1|mt 1 and D t2|mt 1 can be explicitly written as follows:

D t 1 |m t 1 = Nr l=1 Re α * t 1 ,l α t 1 ,l Em + Em ηt 1 ,l - Em 2 Nr l=1 αt 1 ,l 2 (8)
D t 2 |m t 1 = Nr l=1 Re α * t 2 ,l Em ηt 2 ,l - Em 2 Nr l=1 αt 2 ,l 2 (9)
From ( 8) and ( 9), the PEP in ( 7) can be written as shown in [START_REF] Wolniansky | V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel[END_REF] on top of the next page, where we have: i) used the identity Re {ab * } = (1/2) ab * + (1/2) a * b, which holds for 3 The expectation is here computed over fading channel statistics.

PEP (TXt

1 → TXt 2 ) = Pr D t 1 |m t 1 < D t 2 |m t 1 = Pr D t 1 |m t 1 N 0 < D t 2 |m t 1 N 0 = Pr ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ Nr l=1 1 2 α t 1 ,l √ γ + ε t 1 ,l √ γ * α t 1 ,l √ γ + ηt 1 ,l √ N 0 + 1 2 α t 1 ,l √ γ + ε t 1 ,l √ γ α t 1 ,l √ γ + ηt 1 ,l √ N 0 * -1 2 α t 1 ,l √ γ + ε t 1 ,l √ γ 2 < Nr l=1 1 2 α t 2 ,l √ γ + ε t 2 ,l √ γ * ηt 2 ,l √ N 0 + 1 2 α t 2 ,l √ γ + ε t 2 ,l √ γ η * t 2 ,l √ N 0 -1 2 α t 2 ,l √ γ + ε t 2 ,l √ γ 2 ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ (10) PEP (TXt 1 → TXt 2 ) = 1 2 - 1 π +∞ 0 Im Υ (ν) Υ (-ν) exp Δt 1 (ν) Nr l=1 α t 1 ,l 2 + Δt 2 (-ν) Nr l=1 α t 2 ,l 2 ν dν ( 19
)
any pair of complex numbers a and b; ii) normalized to N 0 both decision metrics in order to explicitly show the Signalto-Noise Ratio (SNR) γ = E m /N 0 ; and iii) used [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF].

Let us now define:

d t 1 ,l = A X t 1 ,l 2 + B Y t 1 ,l 2 + CX t 1 ,l Y * t 1 ,l + C * X * t 1 ,l Y t 1 ,l d t 2 ,l = A X t 2 ,l 2 + B Y t 2 ,l 2 + CX t 2 ,l Y * t 2 ,l + C * X * t 2 ,l Y t 2 ,l (11)
where

X t 1,l = α t1,l √ γ + ε t1,l √ γ, Y t 1,l = α t1,l √ γ + ηt1,l √ N 0 , X t 2,l = α t2,l √ γ + ε t2,l √ γ, Y t 2,l = ηt2,l √ N 0 , and A = -1/2, B = 0, C = 1/2.
With these definitions, the PEP in ( 10) can be simplified as follows:

PEP (TXt 1 → TXt 2 ) = Pr {dt 1 -dt 2 < 0} = Pr {dt 1 ,t 2 < 0} (12)
where

d t1 = Nr l=1 d t1,l , d t2 = Nr l=1 d t2,l , d t1,t2 = d t1 -d t2 .
From [12, Sec. III], we note that the PEP in ( 12) can be studied by exploiting the theory of "quadratic-form" receivers in complex Gaussian RVs. More specifically, after a few algebraic manipulations, it can be shown that, when conditioning upon fading channel statistics, d t1 and d t2 are two quadratic forms with CF equal to:

Ψ d t ( ν| αt) = (vav b ) Nr exp vav b (-ν 2 γ t,a +jνγ t,a) (ν+jva)(ν-jv b ) (ν + jva) Nr (ν -jv b ) Nr ( 13
)
where we have emphasized the conditioning upon all the fading channels α i,l for i = 1, 2, . . . , N t and l = 1, 2, . . . , N r in the channel vector α t with t ∈ {t 1 , t 2 }, and have defined:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ γt 1 ,a = γ 2 1 + 1 Nprpm Nr l=1 α t 1 ,l 2 = gt 1 ,a Nr l=1 α t 1 ,l 2 γ t 1 ,b = γ 2 Nr l=1 α t 1 ,l 2 = g t 1 ,b Nr l=1 α t 1 ,l 2 γt 2 ,a = γ 2 Nr l=1 α t 2 ,l 2 = gt 2 ,a Nr l=1 α t 2 ,l 2 γ t 2 ,b = - γ 2 Nr l=1 α t 2 ,l 2 = g t 2 ,b Nr l=1 α t 2 ,l 2 ( 14
)
where

g t1,a = (1/2) γ (1 + 1/(N p r pm )), g t1,b = g t2,a = -g t2,b = (1/2) γ, and v a = (1/4) + N p r pm + (1/2), v b = (1/4) + N p r pm -(1/2).
By taking into account [START_REF] Ney Da Silva | Spectrally efficient UWB pulse shaping with application in orthogonal PSM[END_REF], the CF in ( 13) can be re-written in the very compact form as follows:

Ψ d t ( ν| αt) = Υ (ν) exp ⎛ ⎝ Δt (ν) Nr l=1 α t,l 2 ⎞ ⎠ ( 15
)
where Υ (•) and Δ t (•) are independent of the fading channel gains, and are defined as follows:

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ Υ (ν) = (vav b ) Nr (ν + jva) Nr (ν -jv b ) Nr Δt (ν) = vav b -ν 2 gt,a + jνg t,b (ν + jva) (ν -jv b ) (16)
Let us emphasize that d t1 and d t2 are conditional quadratic forms in complex Gaussian RVs because both the receiver noise and the channel estimation errors are complex Gaussian RVs. Moreover, since noises and channel estimation errors are statistically independent if t 1 = t 2 , then it follows that d t1 and d t2 are two independent quadratic forms. As a consequence, the CF of d t1,t2 in ( 12) can be computed as:

Ψ d t 1 ,t 2 ( ν| αt 1 , αt 2 ) = Ψ d t 1 ( ν| αt 1 ) Ψ d t 2 ( -ν| αt 2 ) (17)
From ( 15) and ( 17), the PEP in ( 12) can be computed from [12, Eq. ( 11)], as follows:

PEP (TXt 1 → TXt 2 ) = 1 2 - 1 π +∞ 0 Im Ψ d t 1 ,t 2 ( ν| αt 1 , αt 2 ) ν dν = 1 2 - 1 π π/2 0 Im Ψ d t 1 ,t 2 ( tan (ξ)| αt 1 , αt 2 )
sin (ξ) cos (ξ) dξ [START_REF] Simon | Digital Communication over Fading Channels[END_REF] which yields an exact, single-integral, and closed-form expression for analysis and design of TOSD-SSK modulation with channel estimation errors.

B. Computation of APEPs

Let us now remove the conditioning upon the fading channel in [START_REF] Simon | Digital Communication over Fading Channels[END_REF]. To this end, we first substitute ( 15) and ( 17) in [START_REF] Simon | Digital Communication over Fading Channels[END_REF], as shown in [START_REF] Van Trees | Detection, Estimation, and Modulation Theory, Part I: Detection, Estimation, and Linear Modulation Theory[END_REF] on top of this page. Then, by averaging over the fading channels, we obtain:

APEP (TXt 1 → TXt 2 ) = E {PEP (TXt 1 → TXt 2 )} = 1 2 - 1 π +∞ 0 Im Υ (ν) Υ (-ν) M A t 1 ,t 2 (ν) (1)
ν dν [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF] where we have introduced the RV A t1,t2 (ν) as follows:

At 1 ,t 2 (ν) = Δt 1 (ν) Nr l=1 α t 1 ,l 2 + Δt 2 (-ν) Nr l=1 α t 2 ,l 2 (21)
In summary, [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF] provides an exact, single-integral, and closed-form expression of the APEP for a generic correlated and non-identically distributed MIMO wireless channel. To compute [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF], only the MGF of RV A t1,t2 (ν) in (21) has to be known in closed-form. This MGF might be computed for a large variety of fading channel models as shown in [START_REF] Simon | Digital Communication over Fading Channels[END_REF]. As an example, let us consider the scenario in which all the wireless links are independent. In this case, M At 1 ,t 2 (ν) (•) reduces to:

M A t 1 ,t 2 (ν) (s) = Nr l=1 M |αt 1 ,l| 2 (sΔt 1 (ν)) × Nr l=1 M |αt 2 ,l | 2 (sΔt 2 (-ν)) (22)
where the MGFs M |α t,l | 2 (•) for t ∈ {t 1 , t 2 } are available in [START_REF] Simon | Digital Communication over Fading Channels[END_REF] for many fading channel models. From ( 22) and [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF], we can observe that the diversity achieved by the TOSD-SSK modulation scheme with a mismatched receiver is the same as the diversity achieved with P-CSI, i.e., 2N r . We will confirm this finding in Section IV with the help of some numerical examples.

IV. NUMERICAL AND SIMULATION RESULTS

In this section, we show some numerical examples to study the performance of TOSD-SSK modulation in the presence of channel estimation errors and compare it with the Alamouti scheme, which similar to TOSD-SSK modulation can offer a diversity gain equal to 2N r [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF]. The simulation setup used in our study is as follows: i) we consider independent Rayleigh fading with normalized unit power over all the wireless links. The MGF needed to compute (22) can be found in [18, Eq. (2.8)]; ii) in TOSD-SSK modulation the rate is qual to R = log 2 (N t ); iii) as far the Alamouti scheme is concerned, we consider Multilevel Phase Shift Keying (M-PSK) modulation with constellation size M and rate R = log 2 (M ); and iv) the orthogonal shaping filters needed in TOSD-SSK modulation are obtained from Hermite polynomials [START_REF] Ney Da Silva | Spectrally efficient UWB pulse shaping with application in orthogonal PSM[END_REF] From Figs. 1-4, we can observe, for various data rates, a very good agreement between Monte Carlo simulations and the analytical framework developed in Section III. By carefully analyzing these figures, the following conclusions can be drawn: i) TOSD-SSK modulation is quite robust to channel estimation errors and only a limited number of pilots N p are needed to get performance very close to the P-CSI lowerbound. In particular, we notice that, in the analyzed scenario, with N p = 10 there is almost no performance penalty; ii) the numerical examples confirm the diversity gain predicted in Section III-B, and we notice a steeper slope when increasing the number of antennas at the receiver. Furthermore, the diversity gain is preserved for any number of pilot pulses, and, so, the quality of the channel estimates; iii) the performance of both TOSD-SSK modulation and Alamouti scheme gets worse for increasing values of the data rate, as expected; iv) TOSD-SSK modulation is worse than the Alamouti scheme when the data rate is low (1 bits/s/Hz), it yields comparable performance for medium data rates (2 bits/s/Hz), while it noticeably outperforms the Alamouti scheme for high data rate (3 bits/s/Hz and 4 bits/s/Hz), while still keeping almost the same computational complexity. This confirms that TOSD-SSK modulation is a good candidate for high data rate applications, and where the data rate can be increased by adding more antennas at the transmitter but still keeping only one of them active at any time instance; and v) the TOSD-SSK modulation scheme is more robust to channel estimation errors than the Alamouti scheme, which agrees with the results obtained in [START_REF] Ulla Faiz | Recursive least-squares adaptive channel estimation for spatial modulation systems[END_REF] where SM is compared to the V-BLAST scheme. This result is very important and breaks with the misconception that the space modulation concept is inherently less robust to inaccuracies in the channel estimation because it maps data information on the impulse response of the wireless channel.

More specifically, the relative robustness of TOSD-SSK modulation with respect to the Alamouti scheme can be quantitatively analyzed in Table I, where we have (approximately) computed the SNRs needed to get ABEP = 10 -4 . For example, we notice that for TOSD-SSK modulation the SNR gap between the setups with P-CSI and N p = 1 is approximately equal to 2dB, while in the same scenario the SNR penalty for the Alamouti scheme is approximately 3dB. Furthermore, the higher robustness of TOSD-SSK modulation to imperfect channel knowledge can be observed by carefully analyzing Table I for a rate equal to 2 bits/s/Hz. We observe that if channel estimation is perfect, the Alamouti scheme is slightly better than TOSD-SSK modulation. However, TOSD-SSK modulation gets slightly better when N p = 1. This example clearly shows the potential benefits of TOSD-SSK modulation in practical scenarios with imperfect channel knowledge.

V. CONCLUSION

In this paper, we have analyzed the performance of the space modulation principle when CSI is not perfectly known at the receiver. A very accurate analytical framework has been proposed and it has been shown that, unlike common belief, transmission systems based on the space modulation concept can be more robust to channel estimation errors than conventional modulation schemes. Furthermore, it has been shown that only few pilot symbols are needed to achieve almost the same performance as the reference scenario with perfect channel knowledge. These results clearly point out the usefulness of the space modulation principle in practical operating conditions, as well as that it can be a promising lowcomplexity transmission technology for the next generation MIMO wireless systems.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .

 1234 Fig. 1. ABEP against Em/N0 for various pilot pulses Np and rate 1 bits/s/Hz. (top) TOSD-SSK modulation: solid lines show the analytical model and markers Monte Carlo simulations. (bottom) Alamouti scheme: only Monte Carlo simulations are shown.

  2, . . . , N t and l = 1, 2, . . . , N r . Furthermore, in TOSD-SSK modulation we have s n (t) = √ E m w n (t) for n = 1, 2, . . . , N t . In particular, (2) is a general N t -hypothesis detection problem [18, Sec. 7.1], [19, Sec. 4.2, pp. 257] in AWGN, when conditioning upon fading channel statistics. Accordingly, the mismatched ML-optimum detector with imperfect CSI at the receiver is as follows:

	m =	argmax	Di	(3)
		m i for i=1,2,...,N t

TABLE I REQUIRED

 I Em/N0 (dB) TO GET ABEP = 10 -4 . THE FIRST AND SECOND LINES SHOW THE SETUP WITH Nr = 1 AND Nr = 2, RESPECTIVELY.

						TOSD-SSK				Alamouti
			Rate		Np = 1	Np = 3	Np = 10	P -CSI	Rate	Np = 1	Np = 3	Np = 10	P -CSI
			1 bits/s/Hz	27.1 18.2	26 16.9		25.5 16.4	25.3 16.2		1 bits/s/Hz	25.3 16.2	23.5 14.5	22.8 13.5	22.3 13.2
			2 bits/s/Hz	28.7 19	27.5 17.8		27 17.3	26.8 17		2 bits/s/Hz	29.1 19.7	27.4 18	26.4 17.1	26.1 16.7
			3 bits/s/Hz	30.2 19.8	29 18.6		28.5 18.2	28.4 17.8		3 bits/s/Hz	33.8 24.7	32.3 23	31.4 22.1	30.8 21.7
			4 bits/s/Hz	31.7 20.7	30.5 19.4		30.1 18.9	29.9 18.7		4 bits/s/Hz	39.4 30.2	37.7 28.6	36.7 27.7	36.4 27.2
	10	0	5	10	15	20	25	30	35	40

(•) * denotes complex-conjugate.

In order to avoid any confusion with the adopted notation, let us emphasize that the subscript n denotes the actual message that is transmitted, while the subscript i denotes the (generic) i-th message that is tested by the detector to solve the Nt-hypothesis detection problem. More specifically, for each signaling interval, n is fixed, while i can take different values at the detector.

ACKNOWLEDGMENT

We gratefully acknowledge support from the European Union (PITN-GA-2010-264759, GREENET project) for this work. Marco Di Renzo acknowledges support of the Laboratory of Signals and Systems (L2S) under the research project "Jeunes Chercheurs". Dario De Leonardis and Fabio Graziosi acknowledge the Italian Inter-University Consortium for Telecommunications (CNIT) under the research grant "Space Modulation for MIMO Systems". Harald Haas acknowledges the EPSRC (EP/G011788/1) and the Scottish Funding Council support of his position within the Edinburgh Research Partnership in Engineering and Mathematics between the University of Edinburgh and Heriot Watt University.


Nicolas Siret

Jean-Franc ¸ois Nezan

Aimad Rhatay

DESIGN OF A PROCESSOR OPTIMIZED FOR SYNTAX PARSING IN VIDEO DECODERS

Keywords: Application-Specific Instruction-set Processor (ASIP), embedded processor, processor architecture, Instruction Set Architecture (ISA), bit manipulation operations, video decoding, circuit design, multimedia

Heterogeneous platforms aim to offer both performance and flexibility by providing designers processors and programmable logical units on a single platform. Processors implemented on these platforms are usually soft-cores (e.g. Altera NIOS) or ASIC (e.g. ARM Cortex-A8). However, these processors still face limitations in terms of performance compared to full hardware designs in particular for real-time video decoding applications. We present in this paper an innovative approach to improve performance using both a processor optimized for the syntax parsing (an Application-Specific Instruction-set Processor) and a FPGA. The case study has been synthesized on a Xilinx FPGA at a frequency of 100 MHz and we estimate the performance that could be obtained with an ASIC.

INTRODUCTION

Ongoing research in the field of video decoding has shown how to implement efficiently video decoders on recent architectures. Usually these architectures are based on DSPs [START_REF] Pescador | A real-time H.264 MP decoder based on a DM642 DSP[END_REF], ASICs [START_REF] Kordasiewicz | ASIC and FPGA implementations of H.264 DCT and quantization blocks[END_REF], or high performance processors. However, DSPs and embedded-processors still face limitations in terms of computing power for applications that require high performance. On the other hand, full hardware solutions on ASICs offer the highest performance and a minimal electrical power consumption but are not flexible. In this paper, we present an advanced hardware-software codesign architecture composed of an Application-Specific Instruction-set Processor (ASIP) and a programmable logical unit (FPGA). Such an architecture is particularly attractive to improve performance while keeping flexibility because it allows the execution of an application to be split into hardware processing for parts that require performance (e.g. IDCT) and software processing for those that require flexibility (e.g. syntax parsing).

Using ASIPs on heterogeneous platforms is an innovative method to improve performance compared to usual embedded processors. Designers can use dedicated instructions that reduce the number of cycles required to execute a program. These dedicated instructions are added to the processor core and to the Instruction Set Architecture (ISA). This offers a good trade-off between flexibility, computing power, and power consumption. This is also a way to decrease the power consumption of a design.

The flexibility offered by embedded-processors on heterogeneous platforms is particularly attractive in the field of multimedia video decoding because it allows the implementation of the application to be updated when new video standards are published. This is also true for the syntax parsing components which extract video data from a compressed bitstream. In fact, it allows complex algorithms (e.g. CABAC) to be added, if necessary, in a second step of development. The syntax parsing is the part of the decoding process which is the least studied in the literature because it is almost sequential and non-optimizable. In a previous paper, we presented a method and results to implement a video decoder on a codesign architecture made up of a general purpose soft-core and FPGA. Performance was restricted by the hardware soft-core generalist architecture and the software syntax parser which was not optimized to be processed on a soft-core [START_REF] Siret | A codesign synthesis from an MPEG-4 decoder dataflow description[END_REF]. This paper presents our work on the codesign architecture, especially on the processor architecture so as to improve performance while keeping flexibility. It makes the following contributions:

• We show the MPEG-4 video decoder implementation on the heterogeneous platform in particular the flexible parser (section 3). The parser takes advantage of a dedicated function called ShowNbits. This function efficiently extracts an arbitrary number of bits from a bitstream no matter the processor architecture.

• We show how to modify the source code of a syntax parser to take advantage of a specific instruction called showbits (section 4). This specific instruction extracts an arbitrary number of bits from a word in a single cycle.

• We present the ASIP hardware architecture and describe how the specific showbits instruction is implemented into the hardware core of the soft-core (section 5).

The paper introduces results obtained with our method for an MPEG-4 video decoder synthesized on a Xilinx Virtex-4 platform at a frequency of 100 MHz. The benefit is about 30% more FPS compared to general purpose soft-core processors.

BACKGROUND

This section presents related work on video decoder implementations, on advanced bit manipulation operations and our approach compared to others.

Application-Specific Instruction-set Processors

ASIPs are general purpose processors with specific instructions added to their Instruction Set Architectures (ISA) that aim to improve performance and to simplify the development of applications. ASIPs offer a good tradeoff between general purpose processors (RISC or CISC architecture) and full hardware solutions (on ASICs) by providing software scalability and better performance than general purpose processors. This results in a reduced time to market for IPs providers and a lower software complexity than fully optimized software solutions.

The hardware implementation of an ASIP consists of a general processor with the addition of specific instructions within the ALU, or functional units within the core [START_REF] Hilewitz | Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors[END_REF][START_REF] Berekovic | Instruction Set Extensions for MPEG-4 Video[END_REF]. In short, the software implementation consists in updating the cross compilation tools, usually GCC/GDB. Thus, the development of an ASIP is carried out in four main steps:

1. updating the core of the processor by adding the hardware code required to process a specific instruction, 2. updating the ISA and the software compiler (e.g. GCC),

3

. adding the specific instruction to the debugger (e.g. GDB) to allow designers to debug their applications, 4. testing and validating the operation of the added instruction on the processor.

In our field of research (i.e. video decoding), adding bit manipulation operations to the core of an ASIP offers significant profits [START_REF] Kim | Bit stream parsing apparatus for audio decoder using normalizing and denormalizing barrel shifters[END_REF]. In fact, these bit manipulation operations are always required to process the syntax parsing while they are not well supported by common general-purpose processor architectures. Indeed, general-purpose processors efficiently process 8, 16, 32-bits size arithmetic operations (e.g. addition, subtraction, multiplication, etc.) but not bit-size operations which are required to extract an element arbitrary. Ongoing research presents various methods [START_REF] Hilewitz | Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors[END_REF][START_REF] Hilewitz | A new basis for shifters in general-purpose processors for existing and advanced bit manipulations[END_REF] to implement these bit manipulation operations. The hardware implementation is usually realized using functional units (i.e. hardware components which process a specific algorithm in parallel with the ALU) added to the core of the processor We chose to add the dedicated instruction within the ALU rather than in independent functional units to avoid modifying the core architecture and processing.

Related Work

Real-time video decoding is difficult to achieve on embedded processors because it requires an efficient implementation and a high-performance processor or DSP [START_REF] Berekovic | Instruction Set Extensions for MPEG-4 Video[END_REF][START_REF] Kneip | The MPEG-4 video coding standarda VLSI point of view[END_REF]. Usually, one or more coprocessors are implemented in addition with the processors to process algorithms that required high performance, like the Inverse Discrete Cosine Transform or the bitstream parsing (i.e. CABAC and CAVLC) [START_REF] Chang | Design and implementation of a bitstream parsing coprocessor for MPEG-4 video system-on-chip solution[END_REF]. However using a coprocessor requires modification of the software code, restricting the code flexibility and portability. On the contrary, ASIPs can be used to keep the software code portability.

In the field of video and audio decoding, syntax parsing extracts bits from a bitstream and transfers these bits to the other video or audio decoding entities [START_REF] Chang | Design and implementation of a bitstream parsing coprocessor for MPEG-4 video system-on-chip solution[END_REF]. To read an arbitrary number of bits from a bitstream, the usual methodology (which is described in the standard) consists of coding and using a ShowNbits function based on bit manipulation operations [START_REF] Berekovic | Instruction Set Extensions for MPEG-4 Video[END_REF]. However, these operations are not well supported by common general-purpose processor architectures.

Researchers have presented methods to efficiently manage bit manipulation operations with results obtained on general purpose processor architectures [START_REF] Kneip | The MPEG-4 video coding standarda VLSI point of view[END_REF], DSPs [START_REF] Pescador | A real-time H.264 MP decoder based on a DM642 DSP[END_REF][START_REF] Berekovic | Instruction Set Extensions for MPEG-4 Video[END_REF] or applications without real-time constraints [START_REF] Hilewitz | Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors[END_REF]. This leads to a lack of exploration of real-time applications implemented on codesign architectures even though they are more and more used. In fact, they offer more performance with a lower power consumption compared to common processor architectures. We complete ongoing research by presenting a complete implementation of a real-time MPEG-4 video decoder on an architecture made up of an ASIP and hardware IPs implemented on a FPGA.

VIDEO DECODING AND SYNTAX PARSING

This section describes the MPEG-4 video decoder architecture and the parsing algorithm that uses the ShowNbits function.

Architecture of a video decoder

The video decoder presented in this paper is one of the applications provided by the Reconfigurable Video Coding [START_REF] Mattavelli | The Reconfigurable Video Coding Standard [Standards in a Nutshell[END_REF][START_REF] Wipliez | Software Code Generation for the RVC-CAL Language[END_REF] (RVC) framework. It is composed of three main parts: the Parser that extracts compressed video data from the bitstream, the AC/DC prediction (sometimes referred as the "(intra, inter) Prediction") that predicts video data from blocks in the same image and the Inverse Discrete Cosine Transform. The MPEG-4 video decoder architecture is introduced in Fig. 1. The video decoder is a dataflow program described as a network composed of the three subnetworks Parser, AC/DC and IDCT2D. Unidirectional optimized FIFOs are implemented between each actor of the networks to ensure the correct transmission of data. The AC/DC and IDCT2D subnetworks are suitable to hardware processing because they are made up of blocks, also called Functional units (FUs), which process almost parallel algorithms (thus data are pipelined). On the other hand, the Parser performs almost sequential algorithms (e.g. reading input bit, storing input bit, looking for start code ...) and thus, is suitable to software processing. The AC/DC and IDCT2D FUs compute video data (4:2:0 configuration) using the decoded data: QP , last, run, value, provided by the Parser.

Syntax parsing algorithm

The scalability of processors is valuable to developing and updating parsing algorithms when new standards are published. All the more so, independently of multimedia applications, these algorithms may be updated and are almost sequential. We implemented the parser on an embedded processor and updated its ISA to evaluate the performance. The MPEG-4 video parser provided by RVC is still limited on embedded processors because it has not been optimized for software processing [START_REF] Siret | A codesign synthesis from an MPEG-4 decoder dataflow description[END_REF]. Thus, we replaced it with a hand-coded parser which has been developed according to the MPEG-4 standard. This parser has been optimized to supply real time video on DSPs [START_REF] ¸ois Nezan | Integration of MPEG-4 Video Tools onto Multi-DSP Architectures using AVSynDEx fast Prototyping Methodology[END_REF]. Moreover, this method is compliant with the RVC framework which encourages the replacement of critical performance FUs by software or hardware IPs.

A detailed description of the MPEG-4 parser is beyond the scope of this paper (but presented in the MPEG standard [START_REF]Information technology -Coding of audio-visual objects -Part 2: Visual[END_REF]). However, an overview of the hand-coded parser is presented in Fig. 2. Ten steps are necessary to extract video data from the compressed video bitstream. In steps (1), ( 2), (3), (4) (within V ideoObjectLayer), the Parser waits for a start code. Depending on the "Video Object" information provided by the start code, it updates the "Video Object Layer"(VOL) or creates a new one. The VOL contains the video object definition and the layer parameters (e.g. image resolution, scalability, etc.) extracted from the bitstream. Then, in steps (5), ( 6) (within V ideoObjectP lane), the parser extracts the frame or plane parameters (e.g. quantification, macroblock type, etc.) and builds the "Video Object Plane" (VOP). Finally, in step ( 7), ( 8) (within DecodeSyntax), the parser computes the video elements (QP , last, run, value) using the VOL and VOP data. In step [START_REF] Chang | Design and implementation of a bitstream parsing coprocessor for MPEG-4 video system-on-chip solution[END_REF], it updates the pointer of the bitstream position. The video elements are sent to the IOs of the processor using an aRDAC specific instruction.

Software implementation of the syntax parsing

The syntax parser component reads bits from the bitstream, realizes tests and sends compressed video data to the other components of the video decoder. To read an arbitrary number of bits from a bitstream, an efficient method consists of coding an optimized ShowNbits function that will be called when necessary. The locations and numbers of bits (which is set for each feature to extract) is defined in the standard. Within the MPEG-4 video parsing software, the ShowNbits function is called more than a thousand times [START_REF] Berekovic | Multimedia RISC core for efficient bitstream parsing and VLD[END_REF] per sequence. Thus, performance of the parsing process depends on the speed of this bit-extraction operation.

The hand-coded parser also uses a ShowNbits function to extract N bits from an M-bit size word. The ShowNbits function requires three arguments: the bitstream, the location of the first bit to read and the number of bits to read. Depending on the processor design, two different algorithms are usually processed. In big-endian architectures, see in Fig. 3, the algorithm first loads part of the bitstream into a register, next left shift the word in register to remove unnecessary left bits, then right shift the word to replace the word in the register (and remove unnecessary right bits) and finally return the result. In little endian architectures, bit mask operations are also necessary.

Our algorithm, presented in Fig. 4, ensures the portability of both architectures. It has the following behavior: Although, the ShowNbits function is quite simple, it requires several cycles to build the M bits size word, to shift and to mask (if necessary) the bits. Hence, a specific instruction which processes these operations allows the performance to be improved [START_REF] Hilewitz | Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors[END_REF][START_REF] Hilewitz | A new basis for shifters in general-purpose processors for existing and advanced bit manipulations[END_REF].

SOFTWARE IMPLEMENTATION OF THE SHOWBITS INSTRUCTION

To improve the performance, we added a showbits instruction into the core of the processor. This instruction loads the data from the bitstream and processes the shifts operations in a single cycle. We present in this section the modifications realized on the ISA to add this specific instruction and the optimizations realized on the software code of the ShowNbits function. These optimizations aim to reduce the number of cycles required to process the ShowNbits function.

Updating the aRDAC Instruction Set Architecture

We updated the cross compilation tools (GCC and GDB) to add the showbits instruction into the ISA. In this way, first we patched the GCC-GDB definition files and then we rebuilt the cross compilation tools. The ISA architecture requires the use of two data registers and an operation code. The operation code defines the instruction for both the processor and the compiler. It is composed of a code operation (i.e. a binary label which identifies an instruction) and two arguments (i.e. two input registers). We define the code operation as showbits, the first argument is the register, which contains the bitstream, and the second argument is the register that contains the location and the size of the N bits word to extract.

Using the showbits instruction within the ShowNbits function

The ShowNbits function can be used, either directly in the C program, or in an assembler part of the program. We chose to hand-write it in assembler to avoid the creation of useless register initialization operations by GCC. As shown on Fig. 5, the updated ShowNbits function has the following behavior:

1. the required variables and registers are initialized (not presented in the figure), 2. the default value of the fixed variables is loaded within registers (e.g. $7, 8, etc.) (not presented in the figure), In addition to these optimizations, the code of the ShowNbits function is inlined by the compiler so as to avoid the loss of cycles due to the function call overhead. This allows the generated assembler code of the parser to be smaller and more efficient.

HARDWARE IMPLEMENTATION OF THE SHOWBITS INSTRUCTION

We present in this section two main points, first the hardware implementation of the showbits instruction within the core of the processor, then the optimizations realized on the processor (in particular on the memory architecture) to improve the performance.

Overview of the "'aRDAC" processor

The Parser is compiled to be processed on an embedded processor. We chose a processor called "aRDAC" because it is a soft-core optimized for embedded targets and has a core that can be modified. It is based on a three stage pipeline Harvard architecture with a CISC type instruction mode, but which operates as a RISC-type processor. Precisely, we worked with the 32-bits version of the aRDAC and we used the aRDAC plug-in (GNU toolchain) for Eclipse IDE which uses GC-C/GDB. The aRDAC is sold by Lead T ech Design1 company.

The aRDAC processor is composed of eight main components shown in Fig. 6. The data and program memories, the memory controller, the ALU and the various registers are usual components of processors. The IO block manages the inputs and outputs of the aRDAC and the transfer block ensures the transmission of the data between the registers and the data memory.

Hardware implementation of the showbits instruction

We added the showbits instruction into the core of the aR-DAC. It is processed in a single cycle to preserve the RISC architecture and the processing performance of one instruction per cycle (i.e. 1MIPS/MHz). This instruction divides by six the number of cycles required to execute the ShowNbits function (see section 6). The showbits hardware processing is introduced in Fig. 7. The behavior of the instruction is pres s s s s s s s s s s s 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Load Processing 0 0 0 0 0 0 0 0 0 0 0 Rsifth s s s s s s s s s s s s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s s s s s s As shown in Fig. 8, we modified the ALU to add the showbits register and the showbits instruction operator. The load from the data memory to the showbits register and the use of a barrel-shifter allow this instruction to be executed in a single cycle, while preserving performance of the processor. The additional hardware cost is nearly null because we used the existing barrel-shifter to process the shift operation, and only add a new single internal register.

Hardware optimizations on the hardware aRDAC architecture

We also updated the memory architecture to optimize the hardware processing, especially when it is necessary to read bits which are not aligned in the memory, in others words, when the M-bits word is split between two consecutive memory addresses (e.g. address n and address n + 1) in the data memory. In such a case, most of the processors need at least two cycles to load a datum and to store it into a register. During the first cycle, the first part of the M-bits word is read at the address n in the memory and stored into a register A. Then, during the second cycle, the second part of the M-bits word is read at the address n + 1 in the memory and stored into the same A register with the correct location. The memory architecture of these processors is called "aligned".

As introduced in Fig. 9, there are two kinds of memory architectures: aligned and non-aligned. A memory built on an aligned architecture allows the access to be aligned only. A memory access is aligned provided that data read from the memory are 8*k bits long (e.g. 8 bits, 16 bits, 32 bits, etc.) and data addresses are l-byte aligned. If a non aligned access is needed on an aligned architecture (e.g. the data starts at the 3 nd byte instead of the 4 th byte), then the memory manager may read two 4-bytes word and store the required part of them in a return register, or it may generate an alignment fault. On the other hand, a memory built on a non-aligned architecture allows the access to be aligned and non aligned.

Currently, most designs use aligned memory address for their simplicity. It is then up to designers to optimize their software code to avoid non-aligned memory access. On the other hand, non-aligned memories offer flexibility and performance but require a more complex hardware logic. The complexity of the memory optimization explains that the use of non-aligned memory architectures in processors are largely patented [START_REF] Anderson | Microprocessor with nonaligned memory access[END_REF][START_REF] David | Microprocessor with non-aligned scaled and unscaled addressing[END_REF]. We modified the memory architecture of the aRDAC to perform non-aligned access. In this way, we updated both the memory manager and the data memory so as to have the following behavior (for load operations):

1. the address is decoded by the memory access block, 2. if an unaligned access is detected, the address is split into a MSB and a LSB address, 3. these two addresses are sent to the memory, 4. the MSB and LSB data are read according to the MSB and LSB address, 5. these data are masked and concatenated depending on the address, 6. the result word is transfered to the result register.

The store operation has similar behavior except that it processes a store operation instead of a load operation.

RESULTS

In this paper we focused on an MPEG-4 video decoder case study but our method is available for other applications. The video decoder was implemented in two parts: the Parser compiled to be executed on the optimized processor and the AC/DC and IDCT2D blocks were synthesized as hardware IPs. Results presented are obtained using Modelsim simulator and Xilinx synthesizer (on a Virtex4 -ML402 evaluation platform).

Results on the ShowNbits function

We have first tested the Parser with two MPEG-4 videos (a CIF and a QCIF resolution) on both the aRDAC and the ASIP.

The ASIP is the version of the aRDAC with the core modifications presented in this paper. Measurements which are introduced in Fig. 10 show that the number of cycles to process the ShowNbits function is divided by almost six using the ASIP. In fact, results show that 65 cycles are required for the pure software solution and only 12 cycles for the optimized software solution. The first call of the ShowNbits function imposes the initialization of dedicated locals registers which consume four additional cycles. The pure software solution requires several shifting operations in addition to data processing (e.g. tfr, add, or, etc.) which is why 65 cycles are needed to process the algorithm. By contrast, the use of the showbits specific instruction dramatically reduces the number of shifting instructions (i.e. two sift operations to build the pos size word) and the number of load instructions (i.e. a single instruction loads the bitstream into a register).

Performance of the MPEG-4 codesign decoder

We then tested the MPEG-4 decoder with the parser compiled for the ASIP and the AC/DC, IDCT2D implemented as IP on the FPGA. The data transfers between the ASIP and the IPs were made through FIFOs. Results presented on Fig. 11 show an increase of 25% of the number of frames per second (FPS). The maximum operating frequency of the ASIP on this FPGA is about 125MHz which allows about 20 FPS to be displayed. Moreover, both synthesis and simulation results point out that the number of FPS increases linearly with the operating frequency which means that newest FPGA (e.g. Virtex-6) allow displaying a real-time CIF video. Nowadays, in the field on embedded processing, real time full HD videos (i.e. 1080p, 30 FPS) are still rarely supported because only full hardware designs on ASICs are able to display such resolutions. In fact, in order to display this resolution it is necessary to compute about 62,208,000 pixels per second which is equivalent to 16 pixels computed every nano-second. On the other hand, real time HDTV video (i.e. 720p 30 FPS) is more and more supported thanks to co-design architectures. On the design presented in this paper and without optimizations, an operative frequency of nearly 1.6GHz for the ASIP is necessary to process a real-time video decoding (2,2GHz with the general purpose ISA).

Finally, we use tools of ASIC creation to get the final performance. Results show that the maximum operative frequency for the aRDAC-ASIP is about 1GHz. This result is interesting because our previous experiences with co-design architectures [START_REF] Siret | A codesign synthesis from an MPEG-4 decoder dataflow description[END_REF] show that several optimizations allow performance of the software to be improved. In this way, we estimate that an operative frequency of nearly 1.2 GHz is necessary to decode HDTV video with an optimized parsing algorithm allowing quasi real-time video decoding. Moreover, with a processor optimized for image processing (the aRDAC is a general purpose processor) it may be possible to decode HDTV video at a frequency under 800 MHz.

CONCLUSION

This paper has presented a method to implement an MPEG-4 video decoder on a heterogeneous platform composed of an ASIP and a FPGA. We have shown the interest of using a specific instruction for the parsing process and how we updated the core (and the ISA) of the processor. We have also presented the modifications made on the memory architecture to improve the performance of the design. Experimental results show a 25% increase of FPS and a decrease of the logical use (nearly 10%) for an additional hardware cost of the processor as almost null. The linear increase of the FPS number with the clock frequency estimate shows that video can be decoded in real time with newest FPGAs (up to a CIF resolution) or ASICs (HD resolution). Therefore, benefits in term of performance compared to usual processor architectures and in term of flexibility compared to full hardware architectures are significant. What is more, processors are almost always used in designs, if only to configure hardware IPs or to process algorithms which do not require performance.

An interesting area for future research involves generating both the hardware and the software code with dedicated instructions using the RVC framework. Another possible area is the development and evaluation of a processor and a software code fully customized for video processing to evaluate the pros (area, performance, power efficiency) and cons (lack of flexibility and portability, programming difficulties) of such a core.

Fig. 1 .

 1 Fig. 1. MPEG-4 video decoder architecture.

Fig. 2 .

 2 Fig. 2. The parsing processes in ten steps.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Execution of the ShowNbits function on a big-endian architecture.

3 .

 3 the current location in the bitstream is computed (not presented in the figure), 4. the location and the size are concatenated in a single word which is stored in the first input register (the location is 4-bits left shifted) (lines 13 to 24 and 29), 5. the required part of the stream is loaded from the data memory and stored in the second input register (line 25),6. the showbits dedicated instruction is called (line 36), 7. finally, the result of the showbits instruction is return (line 40).

  initialization, the bitstream loading, and the // location and the size computing are not presented // in the figure.

Fig. 5 .

 5 Fig. 5. Part of the optimized ShowNbits function which use the showbits instruction.

Fig. 6 .

 6 Fig. 6. The aRDAC processor.

Fig. 7 .

 7 Fig. 7. Execution of the showbits within the ALU. sented below:

Fig. 8 .

 8 Fig. 8. The aRDAC-ASIP processor.

Fig. 9 .

 9 Fig. 9. The two kind of memory architectures: "aligned" and "non-aligned".

Fig. 10 .

 10 Fig. 10. Number of cycles required to process the ShowNbits function, with and without the showbits specific instruction.

Fig. 11 .

 11 Fig. 11. Performance of the codesign MPEG-4 video decoder.

Lead Tech Design : http://www.leadtechdesign.com/