Daniel Thull
email: daniel.thull@st.com

Roberto Sannino
email: roberto.sannino@st.com

Performance Considerations For an Embedded Implementation of OMA DRM 2

Keywords: DRM, Security, Mobile Terminal, Cryptography

As digital content services gain importance in the mobile world, Digital Rights Management (DRM) applications will become a key component of mobile terminals. This paper examines the effect dedicated hardware macros for specific cryptographic functions have on the performance of a mobile terminal that supports version 2 of the open standard for Digital Rights Management defined by the Open Mobile Alliance (OMA). Following a general description of the standard, the paper contains a detailed analysis of the cryptographic operations that have to be carried out before protected content can be accessed. The combination of this analysis with data on execution times for specific algorithms realized in hardware and software has made it possible to build a model which has allowed us to assert that hardware acceleration for specific cryptographic algorithms can significantly reduce the impact DRM has on a mobile terminal's processing performance and battery life.

Introduction

The Open Mobile Alliance, a standardization organization for service enablers in the mobile domain with over 350 member companies [1], has recently completed work on version 2 of its open standard for DRM on mobile terminals. With respect to the first version, OMA DRM 2 provides additional features and a significantly higher level of security so as to protect high-value digital content like polyphonic ringtones, mp3 audio files or video clips on mobile terminals.

Security in OMA DRM 2 is based on a Public Key Infrastructure (PKI) for key distribution and symmetric encryption algorithms for content protection. This paper starts out by describing the actors that are defined by OMA DRM 2 and how they interact in order to grant the final user access to protected content. In chapter 2.4, we take a closer look at the cryptographic operations that are involved in this process. Chapter 0 combines these steps with execution times for different cryptographic algorithms realized in software as well as in hardware and evaluates the impact of hardware acceleration on a mobile terminal's overall performance with respect to execution time and power consumption.

The Standard

The OMA DRM 2 standard consists of three documents. The DRM specification document [START_REF]DRM Specification V2.0[END_REF] defines the communication protocol ROAP as well as general system aspects. The content format for protected media files (Digital Content Format DCF) and the Rights Expression Language (REL), which describes permissions and constraints to govern usage of protected content, are defined in two separate documents.

Actors

The DRM specification document defines four actors that interact with each other in order to provide access to protected digital content to the end-user (see Figure 1). In a procedure not covered by the standard, the Content Issuer (CI), as the owner of digital content, negotiates licenses that grant access to its content with one or more Rights Issuers (RI). Before selling a license to the end-user, the RI sets up a trusted relationship with the DRM Agent, a trusted logical entity residing in the user's terminal. Trust in OMA DRM 2 is based on PKIcertificates issued by a Certification Authority (CA). A valid certificate guarantees that its subject (either the RI or the DRM Agent) adheres to the CA's compliance and robustness rules and can thus be considered trustworthy and secure. Although crucial to the system, the certification process including the definition of compliance and robustness rules is outside the scope of OMA DRM and is left to the business community. The first CA for OMA DRM is called Content Management License Administrator and has been founded in February 2004 [START_REF]CMLA: Content Management License Administrator[END_REF].

Objects

Content and license are delivered to the DRM Agent in two separate logical entities: Content Object (aka DCF although the acronym describes the file format rather than the file itself) and Rights Object (RO). The DCF contains one or more containers that comprise encrypted digital content alongside descriptive meta-data such as author, title and a URL the user may visit in order to obtain a license that allows her to unlock the content.

The Rights Object is realized as an XML file that describes permissions and constraints granted to the DRM Agent when accessing a specific DCF. It also contains the Content Encryption Key (K CEK ) needed to decrypt the DCF as well as the Rights Encryption Key (K REK ) with which the former is encrypted. This two-layer symmetric encryption provides a cryptographic way to decouple content and rights and allows building different licenses for the same content without re-encrypting it. K REK itself is encrypted using the DRM Agent's public key, establishing thus a cryptographic chain that can only be dissolved by the holder of the DRM Agent's private key (Figure 2).

DCF RO Terminal K CEK K REK K MAC K priv 128bit symmetric keys
RSA key

Domains

One important feature of OMA DRM 2 is the possibility to share a license for protected content among a group of devices. In order to do so, the user has to set up a domain and register each participating device with the Rights Issuer, possibly indirectly by using another device as a proxy. During the registration process, the RI relies on a PKI mechanism to provide each trusted device with a secret (symmetric) domain key. This key can subsequently be used by each member device to decrypt K REK of any Domain Rights Object that has been acquired by any member of the group.

By offering the possibility to consume OMA DRM protected content also on devices that cannot directly connect to the RI (the so-called "Unconnected Devices" like mobile mp3 players), the OMA DRM 2 standard broadens its scope well beyond mobile phones. Any device that adheres to a Certification Authority's compliance and robustness rules and owns a valid certificate can thus be used to access protected content.

Phases

The consumption process of DRM protected media can be divided in four phases: Registration, Acquisition, Installation, and Consumption.

Registration -Establishing Trust

In order to prevent leakage of clear content from compromised devices, the Rights Issuer delivers Rights Objects only to trusted DRM Agents, ie those whose certificate has not expired or been revoked. In OMA DRM 2 a trusted relationship gets established when a DRM Agent registers with an RI by following the 4-pass Rights Object Acquisition Protocol (ROAP).

During the first phase of the registration process, both partners advertise their capabilities to each other. This may result in an agreement to use any cryptographic algorithm other than the ones mandated by the standard (see chapter 2.4.5). In the second registration-step, the DRM Agent sends its PKI certificate in a digitally signed message (RegistrationRequest) to the RI. After having verified the message signature and the Agent-certificate's validity -possibly using an Online Certificate Status Protocol (OCSP) request -the RI responds by sending the RegistrationResponse message to the DRM Agent. This message contains the RI's certificate as well as a valid OCSP response for it, indicating whether the certificate has been revoked [START_REF] Meyers | X.509 Internet Public Key Infrastructure Online Certificate Status Protocol -OCSP[END_REF].

Upon reception, the Agent verifies the message signature and the validity of the RI's certificate as well as the OCSP response. If no check has failed, the DRM Agent saves information on the relationship with this specific RI in the RI Context. This data object represents the trusted relationship from the DRM Agent's point of view and its existence, integrity and validity must be verified prior to any future interaction with the RI, such as RO Acquisition.

Acquisition -The Rights Object

In order to acquire a license for a DCF, the DRM Agent checks the existence and validity of an RI Context and sends a digitally signed RORequest message specifying the desired license (Rights Object ID) to the Rights Issuer. If a trusted relationship exists between the parties and payment has been taken care of (the payment process is not within scope of OMA DRM), the RI responds with a digitally signed ROResponse message which contains the protected Rights Object. The Rights Object is integrity-protected by a Message Authentication Code (MAC) and contains a list of Content Object IDs and their respective usage permissions. The MACkey K MAC is protected together with K REK , using a PKI mechanism. The RO is thus not only integrity but also authenticity protected.

Installation -Unwrapping the Keys

After the DRM Agent has extracted the Rights Object from the ROResponse message, it must control its integrity and authenticity before installing the RO on the device. In order to do so, the Agent decrypts C 1 (the first 1024 bits of C which is contained in the RO -see Figure 3) using its private key and obtains Z. Applying the key derivation function KDF to Z yields KEK (key encryption key) which is then used to decrypt C 2 , the last 256 bits of C. As a result of this last decryption, the DRM Agent obtains a concatenation of K MAC and K REK in clear.

After it has successfully checked RO integrity and authenticity using K MAC , the DRM Agent must verify the Rights Object's signature in case it is present, using the RI's public key. This signature is made over certain parts of the Rights Object and is mandatory only for Domain ROs. It is however possible to also sign Device ROs.

The OMA DRM 2 standard does not define technical details on how the DRM Agent shall store Rights Objects and DCFs. This is left to the Certification Authorities to define in their robustness rules. At the time of writing this article, the Content Management License Administrator (CMLA) is the only Certification Authority (CA) for OMA DRM 2 [START_REF]CMLA: Content Management License Administrator[END_REF]. Although different CAs are likely to issue different robustness rules, an obvious requirement that should be common to all is that content and rights are stored in a secure manner. In order for this to happen, four things have to be ensured:

Content confidentiality -Since secure memory is an extremely scarce and costly resource in a mobile terminal, DCFs do not get stored in clear. Thus, content confidentiality is guaranteed. RO integrity is ensured by the MAC that is included in the Rights Object. This implicitly also ensures the connection between RO and DCF since a hash value of the DCF is included in the Rights Object.

RO authenticity -The authenticity of the received Rights Object has been verified when K REK was decrypted successfully. Since it is assumed that only trusted DRM Agents can successfully complete this operation, there is no need to further protect and check authenticity. K CEK , K REK and K MAC confidentiality -Also after installation, K CEK gets protected by K REK . This makes sense because there might be more than one Rights Object for a DCF, so the DRM Agent would have to keep information on the associated keys anyway.

In the original Rights Object, K REK and K MAC get protected by a public key encryption. Since PKI algorithms are very performance intensive, it is desirable to replace them with simpler ones where possible. In this case we chose to substitute the PKI-encryption with a symmetric encryption using a device-generated key K DEV when installing the RO. This is possible because the RO will only be consumed by the installing DRM Agent. This means that the PKI algorithm's main purpose (ie to allow two strangers to share a secret over an insecure channel) is no longer needed and it can be substituted by a less calculation-intensive symmetric cipher. Encrypting K REK and K MAC with K DEV yields C 2dev that can be stored safely in any type of memory (see Figure 3).

Consumption -Steps to Follow for Every Access

Every time the user wants to access protected content, the DRM Agent has to perform the following cryptographic processing steps:

1. Decrypt C 2dev using K DEV 2. Verify RO integrity by checking its MAC 3. Verify DCF integrity by calculating its Hash value and comparing it to the one from within the RO. This is important to bear in mind since these processing steps also apply to small files like ring-tones, because they cannot be stored in clear since secure memory is extremely costly in mobile terminals.

Standard Cryptographic Algorithms

So far we have described the cryptographic operations required by OMA DRM 2 in generic terms. This has been done deliberately since the standard provides the possibility to use other algorithms than the ones that are pre-defined. For the following considerations however, we relied on the standard algorithms, in particular: SHA-1 as Hash function. HMAC SHA-1 as MAC algorithm. 128-bit AES WRAP for en-/decrypting keys. 128-bit AES CBC for content en-/decryption. RSA-PSSA as signature scheme (using the RSASP1 and RSAVP1 primitives as defined in [START_REF]PKCS #1 v2.1: RSA Cryptography Standard[END_REF]). KDF2 as key derivation function as described in [START_REF]DRM Specification V2.0[END_REF]. 1024-bit RSA as PKI function (using the RSAEP and RSADP primitives as defined in [START_REF]PKCS #1 v2.1: RSA Cryptography Standard[END_REF]). A detailed study of the OMA DRM 2 specifications allowed us to build a Java software model of the standard including Rights Issuer, Content Issuer and DRM Agent. The deeper understanding of the cryptographic system implications we obtained from this work, resulted in information about eg the ROAP message file sizes and yielded a list of cryptographic operations carried out in each of the four phases that have been identified above.

For the sake of simplicity we have made close approximations when compiling this list wherever too many details would not have augmented clarity. One example for this is the EMSA-PSS message-encoding mechanism described in [START_REF]PKCS #1 v2.1: RSA Cryptography Standard[END_REF], which we have approximated with just one hash function over the message code.

Costs -Time and Energy

The impact of DRM on overall terminal performance depends to a great extent on the system architecture that provides the supporting functionality. From an end user's perspective, the most important performance-dimensions of a mobile terminal are price, processing time and energy consumption (ie, battery lifetime). A system architect must find he optimal tradeoff between these factors when deciding on whether to support functionality in hardware or in software [START_REF] Ravi | Securing Wireless Data: System Architecture Challenges[END_REF]. This paragraph deliberately neglects DRM impact on monetary terminal costs and concentrates on processing-performance and energy consumption as a result of different architecturechoices.

The underlying assumption for the following considerations is that a mobile terminal contains a System-on-Chip (SoC) that provides all application-related functionality. This element is also known as Application Processor. The SoC consists of various dedicated hardware modules, a general purpose processor core and secure on-chip memory. All these elements are connected by a system bus.

For our performance considerations we relied on the system know-how we had acquired while implementing OMA DRM 2 in Java on a PC as well as publicly available performance figures for the necessary cryptographic algorithms in software and hardware (see Table 1). Following this systemlevel approach, we are currently conducting more detailed experiments that allow for a more accurate consideration of energy consumption. For this paper we assumed energy consumption to be directly related to processing performance. Hence, the estimation figures we obtained regarding processing time can be taken as a first very rough estimate of the effect, the DRM application has on a terminal's energy consumption, although the inherent inefficiencies of protocol-overhead and other non-cryptographic functionality have not been considered.

It is important to note that we deliberately neglected system-related time consumption such as cache-misses or busconflicts in our considerations as these depend on factors such as concurrent applications running that are not strictly related to OMA DRM and there is no generic model that would allow simulating their impact. Furthermore, we concentrated on cryptography-related aspects of OMA DRM and did not take the overhead caused by protocol processing technology like XML parsing into consideration when evaluating the impact of DRM since these components cannot easily be accelerated by dedicated hardware cells.

When facing the challenge to implement a DRM Agent on a mobile terminal, a system designer has to identify crucial processing intensive parts of the application and decide whether to provide these using dedicated hardware cells within a SoC or rather software running on a general purpose processor.

In OMA DRM, the most processing intensive operations that can be realized in hardware are cryptography-related. Security-and price-related considerations apart, dedicated cryptographic hardware modules offer two benefits as compared to software running on a general purpose processor: they are much faster and leave the processor free to do other jobs in parallel.

In order to determine the benefit of different cryptographic hardware accelerators to the OMA DRM application, we calculated the overall processing time needed to perform certain standard operations such as acquiring a Rights Object as well as the relative time spent for each algorithm.

shows the processing time in clock-cycles per data block for each cryptographic algorithm in software (tested on the ARM9 processor) and hardware (with a clock-frequency of less than 200 MHz). Execution times for AES and SHA-1 in hardware were obtained from [START_REF] Bertoni | Architecture for Advanced Cryptographic System[END_REF] whereas the software figures were obtained from internal experiments using standard implementations. Numbers regarding RSA were taken from [START_REF] Mcivor | Fast Montgomery Modular Multiplication and RSA Cryptographic Processor Architectures[END_REF] in the hardware and from [START_REF] Gupta | Performance Analysis of Elliptic Curve Cryptography for SSL[END_REF] in the software case. The constant offset-values for AES and HMAC are due to key-scheduling (AES) and hashing on fixed-length data (HMAC).

We evaluated three architecture variants: a purely software-based approach, a mixed case in which AES and SHA-1 (and thus also HMAC SHA-1) are provided by hardware modules and RSA by software as well as a pure hardware case with dedicated modules for each algorithm. Clock-frequency was assumed to be 200 MHz in each case.

Results -Evaluation of Two Use Cases

Since it is the final user who in the end evaluates terminal performance, measuring DRM's impact cannot be done by examining isolated cryptographic operations but rather by starting from typical use cases. We have identified two of them, decomposed them into single cryptographic steps and based our calculations on the resulting model. The two use cases are:

Music Player: the user has access to an encrypted content file (DCF) of 3.5 Mbytes. In order to obtain a license, she registers with an RI, acquires the license and installs it. She then listens to the track five times. Ringtone: the user has downloaded an encrypted highquality polyphonic ringtone file (size 30 Kbytes). She registers with the RI, obtains a license and installs it. Every time her phone rings, the DRM Agent must now access the encrypted file that is governed by the usage rights in the Rights Object. We assume that she receives 25 calls. The two use cases differ mainly in the size of the encrypted file and in the number of playbacks. For the sake of simplicity, domain functionality has not been included in the examples.

Figure 5 illustrates the percentage of total processing time the processor spends for each cryptographic algorithm (realized as a software program) in both use cases. Because of the larger file size, AES and SHA-1 become much more important in the Music Player use case whereas in the Ringtone use case the PKI algorithms that prevail during the registration-/installationphases play a greater role. The effect of dedicated hardware macros for AES and SHA-1 has thus a much greater effect in the Music Player use case as can be seen in Figure 6 and Figure 7.

In the music player use case, total processing time can be cut to almost a tenth of the value obtained from a pure software implementation by realizing AES and SHA-1 as dedicated hardware macros. In the Ringtone use case, the significant step occurs when providing PKI hardware support.

Hardware acceleration for PKI algorithms has only limited benefits in both use cases from a performance point of view. Since PKI algorithms get only used in the initiating application phases and their execution time does not depend on the DCF size, the absolute figures are identical for both use cases. Given that they total to roughly 600ms (the second column in Figure 7), it is arguable whether or not the costs of a dedicated hardware cell (in terms of transistor gates) are justified by these use cases of the OMA DRM application.

Conclusions and Future Work

As digital content services gain importance in the mobile world, DRM applications will become a key component of mobile terminals. Given the broad support among terminal manufacturers and it being an open standard, OMA DRM 2 is bound to assume a strong position in the standard battle. A detailed study of the cryptographic operations required by OMA DRM 2 has shown that the impact DRM has on processing performance and battery life can be significantly reduced by incorporating hardware acceleration for specific algorithms. For a complete evaluation of the hardware/software partitioning however, also security related aspects have to be considered.

We are currently conducting more detailed simulations regarding energy consumption of dedicated hardware macros for the cryptographic algorithms presented in this article. First results seem to indicate that the gap between software and hardware realizations in this case is even wider than for processing time.

Figure 2 -

 2 Figure 2 -The cryptographic chain that protects content (nodomain case).

Figure 3 -

 3 Figure 3 -Extraction, decryption and encryption of K REK and K MAC during the installation process.

Figure 5 -Figure 6 -

 56 Figure 5 -Relative importance of cryptographic algorithms in both use cases.

Table 1 -Execution times for different cryptographic algorithms in hardware and software.

 1

	Algorithm	Software [cycles]	Hardware [cycles]
	AES Encryption	360 + 830/128 bit	10/128 bit
	AES Decryption	950 + 830/128 bit	10 + 10/128 bit
	SHA-1	400/128 bit	20/128 bit
	HMAC SHA-1	1200 + 400/128 bit	240 + 20/128 bit
	RSA 1024 Public Key Op	2,160,000/1024 bit	10,000/1024 bit
	RSA 1024 Private Key Op	3,774,0000/1024 bit	260,000/1024 bit

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgments

We would like to thank Guido Bertoni and Roberto Zafalon for their support in writing this article.


Keith Holt

Wireless LAN

Keywords: Wireless LAN: Past, Present, and Future Past, Present, and Future

published or not. The documents may come

Introduction

Wireless LAN technology is evolving at a rapid pace. Within just a few years the industry has seen the highest data rates provided by products based on the 802.11 standards migrate from 2 Mbps (802.11) to 11 Mbps (802.11b) and now to 54 Mbps (802.11a/g). Currently, active efforts are underway within the IEEE to define a next generation standard to be known as 802.11n that will enable rates potentially as high as 600 Mbps in a 40 MHz channel. In addition, efforts are also underway to define the 802.11s standard for mesh networking. These developments, as well as potential future technologies such as cooperative diversity, are creating new challenges and opportunities in the design of low power wireless LAN products.

Historical Developments

The development of the air interface for the earliest 802.11 standard was largely driven by regulatory constraints concerning the use of unlicensed spectrum. Rules established in the U.S. by the Federal Communications Commission (FCC) were written primarily to ensure fair and equal access by mandating a certain level of robustness to interference via spread spectrum techniques. The spectral efficiency of the early 802.11 standard was thus rather limited, realizing only 0.1 bps/Hz with a maximum data rate of 2 Mbps in a 20 MHz channel.

Both direct-sequence (DSSS) and frequency hopping (FHSS) forms of spread spectrum were standardized as alternative means of complying with the mandated 10 dB processing gain requirement.

In the development of the 802.11b standard, the maximum data rate was increased to 11 Mbps as the 10 dB processing gain requirement was relaxed in lieu of the transmitted signal maintaining certain essential properties characteristic of a DSSS system. In 802.11b, a combined modulation and coding scheme known as CCK was adopted to increase rate while maintaining a DSSS like signature to other users of the unlicensed band. With CCK, a spectral efficiency of 0.5 bps/Hz was achieved, representing a fivefold increase over the earlier standard.

The large commercial success of wireless LAN products based on these early standards motivated regulatory bodies in many countries around the world to open additional spectrum at 5 GHz for unlicensed use. This time, however, requirements for bandwidth expansion or spreading as a means for resource sharing were sidestepped in favor of allowing more spectrally efficient modulation schemes for support of high data rate applications.

In the 802.11a standard, OFDM was adopted as the means for achieving a wideband spectrally efficient modulation. A maximum data rate of 54 Mbps yielded a spectral efficiency of 2.7 bps/Hz, representing yet again an approximately fivefold increase over the previous standard. With additional regulatory changes, the same OFDM technology was allowed into the 2.4 GHz band and was standardized as 802.11g.

With regulatory barriers to higher spectral efficiency now removed, higher data rates have become limited more fundamentally by technology, not government policy. In fact, the spectral efficiencies achieved by the OFDM based standards were quite good, and essentially represented the best that could be achieved within the practical constraints of cost and range.

Emerging Developments

Fundamental breakthroughs in information theory, which first emerged during the time of the early development of wireless LANs, have now reached a level of maturity and acceptance that is allowing them to drive the quest for higher spectral efficiencies and data rates. So called "MIMO", or multiple-input, multiple-output antenna technology allows spectral efficiencies and hence data rates which were heretofore unreachable. The future 802.11n standard is certain to incorporate this technology, and efficiencies up to 15 bps/Hz are likely to be specified at the highest rate modes which maintains the historical trend of fivefold increases with each new standard. MIMO technology will provide benefits beyond only enhanced data rate. Through the availability of spatial diversity provided by multiple antennas, the range of a wireless LAN network in a fading multipath environment is extended several-fold relative to a conventional signal antenna or SISO system. Other likely enhancements in the 802.11n standard will also increase the range of wireless networks, such as the use of LDPC codes. Even closed loop, transmit side beamforming may be specified in order to improve rate and reach. Another important development in wireless LAN technology is the emergence of mesh networking. Mesh networks have the potential to dramatically increase the area served by a wireless network. Mesh networks even have the potential, with sufficiently intelligent routing algorithms, to boost overall spectral efficiencies attained by selecting multiple hops over high capacity links rather than single hops over low capacity links.

Future Developments

One possible avenue of future development in wireless LAN technology is in the area of "cooperative diversity." Cooperative diversity can be viewed as somewhat of a cross between MIMO techniques and mesh networking. In a cooperative diversity scheme, redundancy in transmission is achieved in a manner analogous with diversity transmission in MIMO. However, the redundant transmission is realized via the cooperation of third party devices rather than solely from the originating device. In a cooperative diversity scheme, third parties which can successfully decode an on-going exchange will effectively regenerate and relay, with appropriate coding, the original transmission in order to improve the effective link quality between the intended parties.

Low Power

These past, present, and future developments create many challenges in the development of low power wireless LAN devices. For example, beginning with the introduction of OFDM, the high peak-to-average ratios characteristic of spectrally efficient modulation have resulted in low power efficiency of the power amplifier and other components in order to achieve the necessary high linearity.

Emerging MIMO technologies create whole new challenges for designers striving to achieve power efficient operation. Multiple transmit and receive RF chains, not to mention the additional baseband processing involved, significantly increase the power consumption over single antenna devices. Advanced coding schemes and increased baseband processing required for beamforming solutions will place additional power demands on future devices.

At the same time, some of these new technologies also provide opportunities to mitigate their increased power appetite through clever product implementation. For example, MIMO systems could reduce power by switching off all but one receive chain until a packet is detected, switching on the additional chains only as required to decode high rate traffic. Closed loop beamforming techniques could allow for effective transmit power control. Finally, mesh or cooperative diversity schemes could "share" some of the power burden with willing third party devices that are less power constrained, such as a device that is drawing power from an electrical outlet rather than a battery.

It is also important that future wireless LAN protocol standards be designed from the outset for low power operation. In computer notebooks, wireless power consumption represents only a fraction of the overall platform power budget. On the other hand, smaller form factor devices impose more stringent power requirements. Wireless LAN protocols currently make few concessions to issues of power management as compared to cellular air interface standards. Undoubtedly, future wireless LAN standards could benefit from more attention in this area.

Conclusions

Wireless LAN technology has experienced extraordinary advances in rate, range, and spectral efficiency. These advances, initially constrained by regulatory policy related to the use of unlicensed spectrum, are now driven entirely by technical innovation and end user application demand which show no sign of abatement. As these new technical innovations continue, the challenges of providing low power operation will continue to mount while new opportunities to lower power consumption will present themselves to innovative designers.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Inalco and the Urdu connection

 Langlès appointed as the head of the Inalco (1796-1824) followed by Silverstre de Sacy (1824-1838).

-First scholarly work on Hindustani > "Monuments anciens et modernes de l 'Hindoustani " (1821) by Langlès.

 1828 > Silvestre de Sacy recommended his student Garcin de Tassy for Hindustani chair.

Garcin de Tassythe scholar of Hindustani

Garcin de Tassy, an orientalist and expert of Hindustani language • Born in Marseille (1794Marseille ( -1878) ) • He knew already Arabic, Persian and Turkish which helped him learning Urdu from 1827 • He never went to India • A great scholar of Islamic texts and Indian culture, particularly Hindustani language • He published more than 150 works including around 20 works on Hindustani language Brief description on origin of Urdu language  Language begins around 12th century, influenced by many languages.  Before 18th century several names of Urdu language -Musulmani Bhasha  Religious period > 1350-1590 -Writing of poems and tracts to diffuse the teaching of religion  Literary works in Urdu > 1590-1730 -Most of the works were produced in Deccan, and in North India it was in Persian  Urdu spoken by speakers of Azimabad

Urdu before British Empire-13 th -14 th centuries Urdu as vehicular language in 18 th century Hindustani as a vehicular language -I  British considered Hindustani the lingua franca of India Colebrook (1808), an officer scholar wrote of Hindustani -Which is used in every part of Hindustan and the Dakhini; which is the common vehicle of colloquial intercourse among all well-educated natives, and among the illiterate also in many provinces of India, and which is almost everywhere intelligible to some among the inhabitants of every village Another scholar [START_REF] Williams | A Practical Hindustani Grammar[END_REF] writes that:

-It is not only the regular spoken language of Delhi, Lucknow and at least fifty millions of persons in Central India, the North West Provinces and the Punjab, but is also the common medium of communication between Musalmaans throughout all India  Chapman mentions it in his Urdu textbook in the early 20 th century : -Hindustani, the lingua franca of India, is a composite language, derived from Sanskrit, Arabic and Persian. It has several recognized varieties of which Urdu and Hindi  British employed Hindustani in the army, in the schools and courts of North India  British learned Hindustani to rule better / to become pukka sahib (authentic master)  Printing presses, radio and film also used more Hindustani

Hindustani as a vehicular language -II  An extract of article from Paris Journal (Le Moniteur Universel, 16/06/1828) by anonymous author cited by [START_REF] Hussain | Garcin de Tassy[END_REF] on the Hindustani language and its teaching at Inalco : -An idiom which, is born from the mixture of Arabic and Persian with Sanskrit, offers the means of communication with the nations which occupy the whole sub-continent of India -Even if we speak 10 to 12 different idioms in different provinces, Indostani is sufficient to foreigners to pass their message in almost every part of this vast region -Other languages such as Bengali, Tamil are limited to their own provinces but Indostani can be regarded as the lingua-franca or the common language of the country  Anonymous 1897 Pamphlet cited by [START_REF] Brass | Language, Religion and Politics in North India[END_REF]



  Establishment in 1669 by Colbert with the name Ecole des jeunes de langue  In 1795, creation of "Ecole spéciale des langues orientales"  Initially started with three posts of professor or Chairs -Vulgar & Literary Arabic -Turkish & Tartar of Crimea -Persian & Malay



  : -Urdu had been a lingua franca of the North for several hundred years, used equally by Hindus and Muslims  Queen Victoria took lessons in the Urdu language Nagari script (Devanagri)  Of uneducated folks (till late 19th century)  Sanskritization began in late 19th century.  Cultural language of Hindus.  Marker of Hinduism  Religious discourses (Hinduism)  Protagonist and Heroes (political & religious)  Rama, Krishna, Bhima, Shivaji  Sardar Patel, Chandara Shekhar Azad  Dialects: Bhojpuri, Chhattisgarhi, Magadhi, Rajasthani, Mewari, Bundelhi, Awadhi, Marwari, Khortha (Census 2001) Urdu  Persian script (Perso-Arabic)  Language of highly educated and elite class (till late 19th & early 20th c)  Language of refinement and upper classes (till early 20th century) Urdu continued to borrow from Persian language. -Cultural language of Muslims -Symbol of Islam  Literary genres (inspired from Iran)  Religious discourses (Islamic)  Different protagonists and heroes (political and religious) -Prophets, Ali, Soufis, Aurangzeb -Maulana Abul Kalam Azad, Muhammad Ali Jinnah  Dialects: Dakhini, Lakhnawi Urdu, Dehlavi, Bambayya Urdu, Pakistani Urdu etc (Rahman 2011) Re-birth of Hindustani language & Urdu as common language of India  Gandhi proposed the re-merging of both Hindi & Urdu -He called it Hindustani -He thought it could be written in either script -He advocated for the infusion of Persian, Arabic, Sanskrit & other indigenous languages into Hindustani -Hindustani of early 20th century different from Hindustani of 19th century  Hindustani was the adopted language of Indian National Congress in 1925  2007 > Sonia Gandhi wrote a letter in Urdu to some prominent Muslims of U.P. seeking their votes, and signed the name in Urdu  Use of the word « jumla » by the BJP Party President  Usage of Urdu by the Indian Foreign Minister on her Pakistan trip (in 2015)  Urdu maintained as a language of the lower courts and police stations  A 74-year-old Hindu man declares Urdu as his mother tongue, he reads Gita in Urdu and all journals and books in Urdu. (Case study by R. Ahmad 2015)  Link of Urdu with Islam in Bangladesh as it is in India and Pakistan  « Urdu should be reclaimed as an integral part of the subcontinent's Islamic culture » (Farrukhi 1989) des fonctionnaires -Plan des formations 08-09 Map of Mumbai local train in Urdu Urdu as vehicular language in Pakistan  Before 1947, Urdu was not spoken in a single household  Only 8 per cent of the total population of Pakistan (Census Pakistan 2001)  75 % of the inscriptions on Pakistani trucks plying on the roads of Pakistan are in Urdu (Rahman 2011) They are mostly Urdu couplets and inscriptions to decorate trucks  Urdu is the most widespread language of Pakistan among ordinary people connected with business activities (Rahman 2011)  Urdu is celebrated as a language of Muslims and its ownership is not shared with the Hindus (Rahman 2011) Urdu in the popular culture Several Pakistani originating actors and musicians Several Urdu lyricists • Considered as a melodious language, many songs use words with Urdu origins • Films of 60s, 70s and 80s dominated by Urdu only songs Big blockbuster movies in Urdu for Indian public • Mughl-e-Azam (The Emperor of the Mughals) Requirement for actors to master Urdu • Urdu classes taken by many actors and actresses Urdu spoken form popularized by Bollywood and TV plays and songs (Rahman 2011) • Songs can be heard on the streets of Delhi, Karachi, Lahore • Oral comprehension by non-Urdu speakers Urdu in Bollywood posters Source: Festival organised by India Culture Lab on Urdu culture now. 8 June 2018. Urdu literary festival : Jashn-e-Rekhtah  Celebrated since two years in India  Around 30 000 people attend from all walks of life -Poets, writers, Urdu scholars -Non-Urdu readers, Urduphiles

  in the streets of Dhaka would understand Urdu • People over 60 have had school level education in Urdu • Urdu film industry prior to 1971 • Hindi has penetrated into the cultural circle, many films and songs in Hindi widely circulated • Around 0.25% of Biharis in Bangladesh > 250,000-300,000 -Community called « stranded Pakistanis », community highly persecuted • News broadcast in Urdu language Nepal • Urdu and Persian usage in royal court was regarded as symbols being cultured • King Pratap Malla (1624-74 A.D.) inscribed Urdu on his coins • Urdu spoken in many parts of Nepal (Naseem 2008) • Qazi Community speaks Urdu (L2) -Numbering around 4,200 • Kashmiri Muslims and Madheshi Muslims speak Urdu • News broadcast in Urdu language • More than 106 Urdu words found in Nepali language L'ASIE DU SUD -HIMALAYA



  Urdu poems on Hindu God (Rama, Shiva) in Devanagari script

Urdu in the Indian sub-continent: some quantitative data

	Country	L1 speakers	L2 speakers	Percentage
	India	85 million		6.70 % (2011 Census)
	Pakistan	14 million	94 million	8%
	Bangladesh	2,50,000		0,14%
	Nepal	692,000	22,900	2,6%

Source : Ethnologue, Census India 2011, World FactBook, CIA.


Frank Kienle
email: kienle@eit.uni-kl.de

Torben Brack
email: brack@eit.uni-kl.de

Norbert Wehn
email: wehn@eit.uni-kl.de

A synthesizable IP Core for DVB-S2 LDPC Code Decoding

The new standard for digital video broadcast DVB-S2 features Low-Density Parity-Check (LDPC) codes as their channel coding scheme. The codes are defined for various code rates with a block size of 64800 which allows a transmission close to the theoretical limits.

The decoding of LDPC is an iterative process. For DVB-S2 about 300000 messages are processed and reordered in each of the 30 iterations. These huge data processing and storage requirements are a real challenge for the decoder hardware realization, which has to fulfill the specified throughput of 255MBit/s for base station applications.

In this paper we will show, to the best of our knowledge, the first published IP LDPC decoder core for the DVB-S2 standard. We present a synthesizable IP block based on ST Microelectronics 0.13µm CMOS technology.

Introduction

The new DVB-S2 standard [START_REF]European Telecommunications Standards Institude (ETSI). Digital Video Broadcasting (DVB) Second generation framing structure for broadband satellite applications[END_REF] features a powerful forward error correction (FEC) system which enables transmission close to the theoretical limit (Shannon limit). This is enabled by using Low-Density Parity-Check (LDPC) codes [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF] one of the most powerful codes known today which can even outperform Turbo-Codes [START_REF] Berrou | The Ten-Year-Old Turbo Codes are Entering into Service[END_REF]. To provide flexibility 11 different code rates ranging from (R = 1 / 4 up to 9 / 10 ) are specified with a codeword length up to 64800 bits. This huge maximum codeword length is the reason for the outstanding communications performance (∼0.7dB to Shannon) of this DVB-S2 LDPC code proposal, so in this paper we only focus on the codeword length of 64800 bits. To yield this performance, the decoder has to iterate 30 times. At each iteration up to 300 000 data are scrambled and calculated. This huge data processing, storage and network/interconnect requirements is a real challenge for the decoder realization.

A LDPC code can be represented by a bipartite graph. For the DVB-S2 code 64800 so called variable nodes (VN) and 64800 * (1 -R) check nodes (CN) exist. The connectivity of these two type of nodes is specified in the standard [START_REF]European Telecommunications Standards Institude (ETSI). Digital Video Broadcasting (DVB) Second generation framing structure for broadband satellite applications[END_REF]. For decoding the LDPC code messages are exchanged iteratively between this two type of nodes, while the node processing is of low complexity. Within one iteration first the variable nodes are procesed, then the check nodes.

For a fully parallel hardware realization each node is instantiated and the connections between them are hardwired. This was shown in [START_REF] Blanksby | A 690-mW 1-Gb/s[END_REF] for a 1024 bit LDPC code. But even for this relatively short block length severe routing congestion problems exist. Therefore a partly parallel architecture becomes mandatory for larger block length, where only a subset of nodes are instantiated. A network has to provide the required connectivity between VN and CN nodes. But realizing any permutation pattern is very costly in terms of area, delay and power.

To avoid this problem a decoder first design approach was presented in [START_REF] Boutillon | Decoderfi rst code design[END_REF]. First an architecture is specified and afterwards a code is designed which fits this architecture. This approach is only suitable for regular LDPC code where each VN has the same number of incident edges, the CN respectively. But for an improved communications performance so called irregular LDPC codes are mandatory [START_REF] Richardson | The Renaissance of Gallager's Low-Density Pariy-Check Codes[END_REF], where the VN nodes are of varying degrees. This is the case for the DVB-S2 code. In [START_REF] Kienle | Design Methodology for IRA Codes[END_REF] we have presented a design method for irregular LDPC codes which can be efficiently processed by the decoder hardware. We used so called irregular repeat accumulate (IRA) codes [START_REF] Jin | Irregular Repeat-Accumulate Codes[END_REF] which are within the class of LDPC codes with the advantage of a very simple (linear) encoding complexity. In general, LDPC code encoder are very difficult to implement due to the inherent complex encoding scheme.

The LDPC codes as defined in the DVB-S2 standard are IRA codes, thus the encoder realization is straight forward. Furthermore, the DVB-S2 code shows regularities which can be exploited for an efficient hardware realization.

Permutation Π degree k

f 3 f j K information nodes (IN)
N parity nodes (PN)

CN

Figure 1. Tanner graph for the DVB-S2 LDPC code

These regularities are also the base for our methodology introduced in [START_REF] Kienle | Design Methodology for IRA Codes[END_REF].

In this paper we show how to exploit these regularities and present an efficient mapping of VN and CN nodes to hardware instances. Memory area and access conflicts are most critical in this mapping process. Thus we used simulated annealing to minimize memory requirements and avoidance of RAM access conflicts.

We present to the best of our knowledge the first IP core capable to process all specified code rates in the DVB-S2 standard. We show synthesis results using a 0.13µm technology.

The paper is structured as follows: the DVB-S2 LDPC codes and the decoding algorithm are presented in Section 2. In Section 3 the mapping of nodes to hardware instances is explained. The overall decoder architecture is shown in Section 4. Section 5 gives synthesis results and Section 6 concludes the paper.

DVB-SLDPC Codes

LDPC codes are linear block codes defined by a sparse binary matrix (parity check matrix) H. The set of valid codewords x ∈ C have to satisfy

Hx T = 0, ∀x ∈ C. ( 1
)
A column in H is associated to a bit of the codeword and each row corresponds to a parity check. A nonzero element in a row means that the corresponding bit contributes to this parity check. The code can best be described by a Tanner graph [START_REF] Richardson | The Renaissance of Gallager's Low-Density Pariy-Check Codes[END_REF], a graphical representation of the associations between code bits and parity checks. Code bits are shown as variable nodes (circles), and parity checks as check nodes (squares), with edges connecting them. The number of edges on each node is called the node degree. If the node degree is identical for all variable nodes, the corresponding parity check matrix is called regular, otherwise it's irregular.

By carefully inspection of the construction rules, the DVB-S2 parity check matrix consists of two distinctive parts: a random part dedicated to the systematic information, and a fixed part that belongs to the parity information.

The Tanner graph for DVB-S2 is shown in Figure 1. There exist two types of variable nodes, the information (IN) and parity nodes (PN), corresponding to the systematic and parity bits respectively. The permutation Π represents the random matrix part of the connectivity between IN and CN nodes, while the PN nodes are all of degree two and are connected in a fixed zigzag pattern to the CN nodes. The N check nodes have a constant degree k. The K information nodes consist of two subsets f j and f 3 , with f the number of IN nodes of degree j and 3. Table 1 summarizes the code rate dependent parameters as defined in the standard [START_REF]European Telecommunications Standards Institude (ETSI). Digital Video Broadcasting (DVB) Second generation framing structure for broadband satellite applications[END_REF]. The connectivity of the IN and CN nodes is defined by the DVB-S2 encoding rule

p j = p j ⊕ i m , j = (x + q(m mod 360)) mod N. ( 2
)
p j is the jth parity bit, i m the mth information code bit, and x, q, and N are code rate dependent parameters specified by the DVB-S2 standard. Equation 2 determines the entries of the parity check matrix. The mth column has nonzero elements in each row j, thus the permutation Π generates one edge between every CN m and IN j.

The fixed zigzag connectivity of the PN and CN nodes is defined by the encoding scheme:

p j = p j ⊕ p j-1 , j = 1, 2, ..., N -1. (3)
This is a simple accumulator. The corresponding part of the parity check matrix has two nonzero elements in each column, forming a square banded matrix. This type of LDPC codes with this simple encoding procedure are also called irregular repeat accumulate (IRA) codes [START_REF] Jin | Irregular Repeat-Accumulate Codes[END_REF].

Decoding Algorithm

LDPC codes can be decoded using the message passing algorithm [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF]. It exchanges soft-information iteratively between the variable and check nodes. The update of the nodes can be done with a canonical scheduling [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF]: In the first step all variable nodes must be updated, in the second step all check nodes respectively. The processing of individual nodes within one step is independent, and can thus be parallelized.

The exchanged messages are assumed to be loglikelihood ratios (LLR). Each variable node of degree i calculates an update of message k according to:

λ k = λ ch + i-1 ∑ l=0,l =k λ l , (4)
with λ ch the corresponding channel LLR of the VN and λ i the LLRs of the incident edges. The check node LLR updates are calculated according to

tanh(λ k /2) = i-1 ∏ l=0,l =k tanh(λ l /2). (5)
For fixed-point implementations it was shown in [START_REF] Zhang | On fi nite precision implementation of low-density parity-check codes decoder[END_REF] that the total quantization loss is ≤ 0.1db when using a 6 bit message quantization compared to infinite precision. For a 5 bit message quantization the loss is 0.1-0.2 dB [START_REF] Richardson | The Renaissance of Gallager's Low-Density Pariy-Check Codes[END_REF].

Optimized update of degree 2 Parity Nodes

The DVB standard supports LDPC codes ranging from code rate R = 1 / 4 to R = 9 / 10 . Each code has one common property: the connectivity of the check nodes caused by the accumulator of the encoder. CN 0 is alway connected to CN 1 by a variable node of degree 2 and so on for all CN nodes. A variable node of degree 2 has the property that the input of the first incident edge is the output of the second incident edge (plus the received channel value) and vice versa. For a sequential processing of the check nodes (e.g. from left to right in Figure 1) an already updated message can directly passed to the next check node due to the simple zigzag connectivity. This immediate message update changes the con- 2. Only the connectivity between check nodes and parity nodes is depicted, the incident edges from the information nodes are omitted. Figure 2a) shows the standard belief propagation with the two phase update. In the first phase all messages from the PN to CN nodes are updated, in the second phase the messages from CN to PN nodes respectively. The message update within one phase is commutative and can be fully parallized. Figure 2b) shows our new message update scheme in which the new CN message is directly passed to the next CN node. This data flow is denoted as a forward update and corresponds to a sequential message update. The backwards update from the PN to CN nodes is again a parallel update. Note that a sequential backwards update would result in a maximum a posteriori (MAP) algorithm.

Rate

This new update scheme improves the communications performance. For the same communications performance 10 iterations can be saved i.e. 30 iterations instead of 40 have to be used. Furthermore we need to store only one message instead of two messages for the next iteration, which is explained in more detail in Section 4.

Hardware mapping

As already mentioned only partly parallel architectures are feasible. Hence only a subset P of the nodes are instantiated. The variable and check nodes have to be mapped on these P functional units. All messages have to be stored during the iterative process, while taking care of RAM access conflicts. Furthermore we need a permutation networks which provides the connectivity of the Tanner graph. 2 for each code rate. Furthermore the q factor of Equation 2 is listed. The implementation of E IN is the challenging part, since this connectivity (Π) changes for each code rate. The realization of E PN is straightforward, thus we focus on the mapping of the IN and CN nodes.

Due to the varying node degrees the functional nodes process all incoming messages in a serial manner. Thus a functional node can except one message per clock cycle and produces at most one updated message per clock cycle.

A careful analysis of Equation 2shows that the connectivity of 360 edges of distinct information nodes are determined by just one value x, while q is a code rate dependent constant, see Table 2.

These 360 edges can be processed simultaneously by P = 360 functional units. Within a half iteration a functional unit has to process q * (k -2) edges. (k -2) is the number of edges between one check node and information nodes. For each code rate q was chosen to satisfy the constraint

E IN /360 = q * (k -2). ( 6
)
It guarantees that each functional unit has to process the same amount of nodes which simplifies the node mapping. Figure 3 shows the mapping of the IN and CN nodes for the LDPC code of rate R = 1 / 2 . Always 360 consecutive VN nodes are mapped to 360 functional units. To each func-tional unit a RAM is associated to hold the corresponding messages (edges). Please note that for each IN of degree 8, 8 storage places are allocated to this VN, because each incident edge has to be stored.

The check nodes mapping depends on the rate dependent factor q. For R = 1 / 2 the first q = 90 CN nodes are mapped to the first functional unit. The next 90 CN nodes are mapped to the next producer and so on. Again the CN number corresponds to CN degree storage locations.

This node mapping is the key for an efficient hardware realization, since it enables to use a simple shuffling network to provide the connectivity of the Tanner graph. The shuffling network ensures that at each cycle 360 input messages are shuffled to 360 distinct target memories. Thus we have to store E IN /390 = 450 shuffling and addressing information for the R = 1 / 2 code, see Table 2 for the other code rates. The shuffling offsets and addresses can be extracted from the x tables provided by [START_REF]European Telecommunications Standards Institude (ETSI). Digital Video Broadcasting (DVB) Second generation framing structure for broadband satellite applications[END_REF].

Decoder Architecture

Based on the message mapping described in the previous chapter, the basic architecture of the DVB-S2 LDPC decoder is shown in Figure 4. It consists of functional units which can process the functionality of variable and check nodes. This is possible, since only one type of the node are processed during one half iteration. The IN message memories banks hold the messages which are exchanged between information and check nodes. Furthermore we have memories for storing the exchanged messages for the parity nodes (PN message memories), which are all of degree two. The address and shuffling RAM together with the shuffling network provides the connectivity of the Tanner graph.

As mentioned the decoder processes 360 nodes in parallel so 360 messages have to be provided per cycle. All 360 messages are read from the same address from the IN message memory bank. Though, for the information node processing we just increment the reading address. The functional unit can accept each clock cycle new data, while a control flag just labels the last message belonging to a node and starts the output processing. The newly produced 360 messages are then written back to the same address location but with a cyclic shift, caused by the shuffling network. To process the check nodes we have to read from dedicated addresses, provided by the address RAM. These addresses were extracted from node mapping as described in the previous chapter. Again 360 messages are read per clock cycle and written back to the same address after the processing via the shuffling network. This ensures that the messages are shuffled back to their original position.

The processing of the parity nodes can be done concurrently during the check node processing, by using the update scheme described in Section 2.2. Each functional unit processes consecutive check nodes (Figure 3). The message which is passed during the forward update of the check nodes is kept in the functional unit. Only the messages of the backward update has to be stored which reduces the memory requirements for the zigzag connectivity to E PN /2 messages. The PN message memories are only read and written during the check node phase, while the channel (CH) RAMs delivers the corresponding received channel value.

We use single port SRAMs due to area and power efficiency. Hence we have to take care of read/write conflicts during the iterative process. Read/write conflicts occur, since data are continously read from the 360 RAMs and provided to the functional units, while new processed messages have to be written back.

The check node processing is the most critical part. We have to read from dedicated addresses extracted during the mapping process. Therefore, the IN message memory block is partitioned in 4 RAMs which is shown in Figure 5. Even if the commutativity of the message processing within a check node is exploited all write conflicts can not be avoided. Therefore a buffer is required to hold a message if writing is not possible due to a conflict. We use simulated annealing to find the best addressing scheme to reduce RAM access conflicts and hence to minimize the buffer overhead. This optimization step ensures that only one buffer is required which holds for all code rates. Per clock cycle we read data from one RAM, and write at most 2 data back to two distinct RAMs, coming from the buffers or the shuffling network. The two least significant bits of the addresses determines the assignment to a partition. This allows a simple control flow, which just has to compare the reading and the writing addresses of the current clock cycle.

The resulting decoder throughput T is

T = I #cyc • f cyc , (7)
with I the number of information bits to be decoded and #cyc the number of cycles to decode one block including the input/output (I/O) processing.

The number of cycles is calculated as

T = I C P IO + It • 2 • ( E IN P + T latency ) • f cycle . (8)
The part C P IO is the number of cycles for input/output (I/O) processing. The decoder is capable to receive 10 channel values per clock cycle. Reading a new codeword of size C and writing the result of the prior processed block can be done in parallel with reading/writing P IO data concurrently. The latency T latency for each iteration depends on the processing units and the shuffling network.

Results

The LDPC decoder is implemented as a synthesizable VHDL model. Results are obtained with the Synopsis Design Compiler based on a ST Microelectronics 0.13µm CMOS technology. The maximum clock frequency is 270 MHz under worst case conditions. The decoder is capable to process all specified code rates of the DVB standard with Table 3 shows the synthesis results for a 6 bit message quantization of the channel values and the exchanged messages. The overall area is 22.74mm 2 . The area is determined by different code rates. R = 1 / 4 has the largest set of parity nodes and defines the size of the PN message memories. While the rate R = 3 / 5 has the most edges to the informtion nodes and hence determines the size of the IN message memory banks. The size of a functional node depends on the maximum IN and PN degree, respectivly (R = 2 / 3 and R = 9 / 10 ).

The area is splitted in three parts: RAMs, logic and the shuffling network. Storing the messages yields the major part of the RAM area with 9.12mm 2 . It is important to note, that only an area of 0.075mm 2 is required to store the connectivity of the Tanner graph. This shows the efficiency of our architectural approach. The logic area of the functional nodes with 10.8mm 2 is a major part of the overall area. This is due to the required flexibility of the different code rates. We also placed and routed the shuffling network to test routing congestions. Due to its regularity no congestions resulted, its area is dominated by the logic cells.

Conclusion

Low-Density Parity-Check codes are part of the new DVB-S2 standard. In this paper we presented to the best of our knowledge the first published IP core for DVB-S2 LDPC decoding. We explained how to explore the code structure for an efficient hardware mapping and presented a decoder architecture which can process all specified code rates ranging from R = 1 / 4 to R = 9 / 10 .

Figure 2 .

 2 Figure 2. a) conventional message update scheme b) optimized message update scheme

Figure 3 .

 3 Figure 3. Message and functional unit mapping for R = 1 / 2

Figure 4 .

 4 Figure 4. Basic architecture of our LDPC decoder

Figure 5 .

 5 Figure 5. Hierarchical RAM structure

Table 1 . Parameters describing the DVB-S2 LDPC Tanner graph for different coderates

 1

	Rate	j	f j	f 3	k	N	K
	1 / 4	12 5400 10800 4 49600 16200
	1 / 3	12 7200 14400 5 43200 21600
	2 / 5	12 8640 17280 6 38880 25920
	1 / 2	8 12960 19440 7 32400 32400
	3 / 5	12 12960 25920 11 25920 38880
	2 / 3	13 4320 38880 10 21600 43200
	3 / 4	12 5400 43200 14 16200 48600
	4 / 5	11 6480 45360 18 12960 51840
	5 / 6	13 5400 48600 22 10800 54000
	8 / 9	4	7200 50400 27 7200 57600
	9 / 10	4	6480 51840 30 6480 58320

Table 2 . Code rate dependent parameters, with E the number of incident edges of IN and PN nodes and Addr the number of values re- quired to store the code stucture

 2

		q	E PN	E IN	Addr
	1 / 4	135 97199 97200	270
	1 / 3	120 86399 129600	360
	2 / 5	108 77759 155520	432
	1 / 2	90 64799 162000	450
	3 / 5	72 51839 233280	648
	2 / 3	60 43199 172800	480
	3 / 4	45 32399 194400	540
	4 / 5	36 25919 207360	576
	5 / 6	30 21599 216000	600
	8 / 9	20 14399 180000	500
	9 / 10	18 12959 181440	504
	ventional update scheme between CN an VN nodes (Equa-
	tion 4).
	The difference in the update scheme is presented in Fig-
	ure

Table 3 . Synthesis Results for the DVB-S2 LDPC code decoder

 3

	0.13µm technologie	AREA
			[mm 2 ]
		channel LLRs	1.997
	RAMs	Messages	9.117
		Address/Shuffling	0.075
	Logic	Functional Nodes	10.8
		control logic	0.2
	Shuffling Network	0.55
	Total Area [mm 2 ]	22.739

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgments

The work presented in this paper was supported by the European IST project 4More 4G MC-CDMA multiple antenna system On chip for Radio Enhancements [10].

Our special thanks goes to Friedbert Berens from the Advanced System Technology Group of STM, Geneva, Switzerland, for many valuable discussions.


Andrew Duller
email: andy.duller@picochip.com

Daniel Towner

Gajinder Panesar

Alan Gray

Will Robbins

picoArray technology: the tool's story

come   L'archive ouverte pluridisciplinaire

Introduction

The wireless communications field is experiencing a period of major expansion. This is happening all over the world and is not dominated by any one region in particular. In a field in which different standards are fixed for different regions of the world, where standards are in a state of flux or even where no standards exist, it is very costly to enter the market with a custom ASIC solution. What is required is a scalable programmable solution, which can cater for most, if not all, of these areas. To this end the picoArray and a rich toolset have been created.

The picoArray is a tiled processor architecture in which hundreds of processors are connected together using a deterministic interconnect [START_REF] Duller | Parallel Processing -the picoChip way![END_REF][START_REF] Claydon | A Massively Parallel Array Processor[END_REF]. The level of parallelism is relatively fine grained with each processor having its own small amount of data and instruction memory. Each processor runs a single process in its own memory space and uses "signals" to synchronise and communicate. Multiple picoArray devices may be connected together to form systems containing thousands of processors using peripherals which effectively extend the on-chip bus structure.

In order to provide a massively parallel, scalable solution that is commercially viable, it has been necessary to re-think methods of debug and verification in the following areas: Scale Depending upon the target, systems solutions may require moderate or massive computational power. To address this, many picoArray devices may be connected together 1 , creating systems containing thousands of processors.

Reduced non-essential hardware Specialised hardware for anything other than computation must be justified and the emphasis should be on system-wide rather than processor-centric debug hardware. Therefore conventional support, such as register or memory trace mechanisms, is not as useful as in a uni-processor system. In the picoArray, hardware support for debug has been kept to a minimum in order to allow more processors to be fitted onto a single device.

Environment The picoArray devices are designed for use in embedded environments where there are relatively few inputs and outputs. In such environments, the bandwidth available for debugging traffic is limited.

Relatively light weight access is provided to the pi-coArray via a JTAG interface and the external processor interface.

Communication and synchronisation

Many parallel systems use special purpose libraries (e.g., Posix threads [START_REF] Butenhof | Programming with POSIX Threads[END_REF], Message Passing Interface [START_REF] Pacheco | Parallel Programming with MPI[END_REF]) or language support mechanisms (e.g., Java threads [START_REF] Inc | Threads: Doing two or more tasks at once[END_REF]) to handle communication and synchronisation of parallel processes. This is very difficult to justify in an embedded system where memory cost is an area of concern. The picoArray uses a deterministic interconnect fabric called the picoBus. This behaves like a handshaken FIFO between processes, and is used for communication and synchronisation. No run-time arbitration of the picoBus is necessary, leading to simpler hardware and removing a possible source of bugs.

Conventional debuggers are usually designed for a single processor, and normally require a reasonable amount of hardware support. Even debuggers from vendors who claim to support multi-processor systems will require hardware support. More importantly, however, conventional debuggers will not scale to systems consisting of hundreds or thousands of processors.

The approach to debug and verification has been to exploit the programming paradigm provided by the picoArray [START_REF] Duller | Parallel Processing -the picoChip way![END_REF][START_REF] Claydon | A Massively Parallel Array Processor[END_REF] and to create a rich set of tools to aid systemwide debug and verification. The approach can be divided into two main aspects: language features and software tools.

The picoArray tools support an input language which is a combination of VHDL [START_REF] Ashenden | The Designer's Guide to VHDL[END_REF], ANSI/ISO C and assembly language. Individual processes are written in C and assembler, while structural VHDL is used to describe how processes are connected together using signals. Signals are strongly typed, and have specified bandwidths. They may be synchronous or asynchronous, point-to-point or point-to-multipoint. Processes are statically created by describing their number and type in the source files -no runtime creation of processes is possible. Thus, after a system has been compiled, the complete set of processes and their connectivity is known, which ensures that the system will behave deterministically.

The most common software tool for debugging is the symbolic debugger, which allows the programmer's original source code to be displayed, along with the contents of source variables, on a per-process basis. The use of symbolic debugging is commonplace, so will not be considered further in this paper. The additional mechanisms that have been developed are the following: design browser This allows both static and dynamic analysis of a user's design. The overall structure of a system can be graphically displayed in a number of ways. This allows the user to verify that the overall system has been connected in the way that was intended and to visualise and navigate through a complex design which may have been coded by many people. In addition, dynamic analysis can be performed and it can be used to visualise problems such as those associated with data throughput and deadlock.

simulation The cycle accurate simulator allows all of the processor's internal state to be viewed, including aspects that the real hardware does not allow access to. Typically the user would start their development here and then migrate to hardware.

scripting The debugger can be programmed using Tcl/Tk. This allows the user to build on the basic system provided by the standard debugger.

probes These are processes which can be inserted into a user's design during debugging, to enable complex real-time analysis.

file I/O Data can be streamed in to and out of a system using files.

Switch Processor

Example signal path

Figure 1. picoArray Interconnect

The remainder of this paper gives an overview of picoArray devices, a brief description of each debug mechanism, and then shows how the debug and verification tools might be used over the lifetime of a design, from initial component to integrated system.

The picoArray Concept

The picoArray Architecture

The latest device -PC102 is based around the picoArray tiled processor architecture in which over 300 processors (3-way VLIW, Harvard architecture with local memory), and 14 co-processors (Function Accelerator Units or FAUs) are interconnected by a 32-bit picoBus and programmable switches.

The term Array Element (AE) is used to describe either processors or co-processors (i.e. there are 322 AEs in the array). There are three processor variants which share the same basic structure: Standard AE (STAN), Control AE (CTRL) and Memory AE (MEM). The memory configuration and number of communications ports varies between AE types.

Inter-processor Communications

Within the picoArray core, AEs are organised in a two dimensional grid, and communicate over a network of 32bit buses (the picoBus) and programmable bus switches. AEs are connected to the picoBus by ports. The ports act as nodes on the picoBus and provide a simple interface to the bus based on put and get instructions.

The inter-processor communication protocol is based on a time division multiplexing (TDM) scheme, where data transfers between processor ports occur during time slots scheduled automatically by the tools and controlled using the bus switches. The bus switch programming and the scheduling of data transfers is fixed at compile time and requires no run-time arbitration. Figure 1 shows an example in which the switches have been set to form two different signals between processors. Signals may be point-to-point or point-to-multi-point. In the latter case, the data transfer will not take place until all the processor ports involved in the transfer are ready. The total internal data bandwidth for the signals is 3.3 Tera-bits per second 2 .

The default signal transfer mode is synchronous; data is not transfered until both the sender and receiver ports are ready for the transfer. If either is ready before the other then the transfer will be retried during the next available time slot. If, during a put instruction, no buffer space is available then the processor will sleep (hence reducing power consumption) until space becomes available. In the same way, if during a get instruction there is no data available in the buffers then the processor will also sleep. This protocol ensures that no data can be lost.

There is also an asynchronous signal mode where transfer of data is not handshaken and in consequence data can be lost by being overwritten in the buffers without being read.

External Communications

The picoArray has three methods of external communications. They are:

• External Processor Interface (EPI),

• Inter-picoArray Interface (IPI),

• Asynchronous Data Interface (ADI).

These can all be connected to the picoBus and can be accessed using signals. The EPI can be used to configure pi-coArray devices and can be used by debugging tools for input and output of (2.5 Giga-bits per second) information.

The IPI is used to connect picoArray devices together and can be viewed as a way of extending the picoBus across devices.

The ADI is used for exchanging data with high bandwidth (5 Giga-bits per second) external asynchronous data streams.

Each device has a single EPI and four interfaces each of which can be configured as either an IPI or an ADI.

picoArray Debug and Analysis

Language Features

The language features aid verification and integration through three main features: strong type checking, fixed process creation, and bandwidth allocation. Strong type checking is used to ensure that whenever data is communicated from one process to another, the data will be interpreted by both producer and consumer in the same way. Types are selected from a library of built-in types, or by the user defining their own types. Types used in communication are limited to 32-bits, which is the maximum size which may be transferred in a single communication over the picoBus. At the structural level, processes will be defined with ports of specific types, and they will be connected with signals which must match the port types. Within a process, any data which is put or get from a port must be of the correct type. For processes written in C, this is achieved by synthesising the available types using C encoding rules (e.g., using typedef's, union's, and struct's), and hence tying in to the C compiler's type system. Thus, end-to-end communication of data can only occur when all processes and signals agree on the type format. This facilitates integration of independently developed components since any discrepancies in type formats will be detected at compile time.

The structural VHDL used to define a system requires the number of processes, and their interconnections, to be fixed at compile time. During compilation, the tools will allocate each process to its own processor and schedule the signals connecting the processes on to the picoBus interconnection fabric. Because of this compile-time scheduling, non-deterministic runtime effects such as process scheduling or bus contention have been eliminated. This makes it easier to integrate systems. If problems are found, it also makes the reproduction of the problems, their debugging and the verification of their fixes easier.

In addition to specifying fixed signals connecting processes, the signals are also allocated bandwidth. This is achieved using a language notation which allows the frequency of communication over the signal to be specified. Processes requiring high signal bandwidths will use high frequencies (e.g., every 4 cycles), while processes requiring low bandwidth will use low frequencies (e.g., every 1024 cycles).

Design Browser

The design browser is a tool which allows the user's logical design to be viewed graphically and can be used both during simulation and when executing a design on hardware. The following different graphical views are possible:

• hierarchical,

• flat within a given scope,

• as the strongly connected components (SCC).

The hierarchical view mirrors the structural hierarchy that was created by the user and allows each level of this hierarchy to be explored. An example of this is shown in figure 2.

Figure 2. Design browser hierarchical display

There are times when the user wishes to see more of a design than is permitted by the hierarchy display, and the "flat" display provides this. If displayed from the root of the design the entire design is displayed at once. In addition, by displaying from a scope other than the root, subtrees of the design can be viewed. The major difference between this and the hierarchy display is that from a given scope all of the leaf instances are displayed at once.

The final view comes from thinking of a design as a directed graph and then producing a single level of hierarchy by identifying the strongly connected components (SCC). Each of these components can be viewed on their own. An example of this is shown in figure 3. The importance of the SCC view is that from the root level the graph becomes acyclic (a directed acyclic graph) and this gives advantages when trying to debug a system which has deadlock, livelock or data throughput problems, because it separates out the parts of the design that contain feedback from those that are simply pipeline processing.

In addition to these static features the design browser can provide dynamic information about the each instance in a design, for example whether it is processing or waiting for a communications operation. An example of this display is shown in figure 3 where the boxes are coloured green for processing and red for waiting on communications.

Simulation

The cycle accurate simulation system allows users to build, test and verify their entire design before moving to the hardware. The user is able to extract the state of the system (on a cycle-by-cycle basis) in order to check against the behaviour on hardware. Importantly, the same simulation system was used to provide a "golden reference" during the design and verification of the PC101 and PC102 chips.

The same source-level debugging interface exists on the hardware as on the simulator, enabling the user to migrate

Scripting

While debugging large parallel systems, operations such as viewing the source code or variable values of individual processes become too low level; this is analogous to debugging a compiled process by inspecting its raw machine code and register values. For large parallel systems it is more convenient to be able to abstract the debugger to provide a higher, system-level interface. Such an interface allows the details of individual processes to be hidden, and replaced by system-specific displays. Clearly, it is impossible to provide interfaces for every possible system, so instead the debugger can be programmed using Tcl/Tk [START_REF] Ousterhout | Tcl and the Tk Toolkit[END_REF]. This allows the users to create their own system-specific interfaces, built on top of the debugger.

FileIO

When testing and debugging it is common to wish to use disk files in order to inject data into a system or to record intermediate results. This is achieved by providing an AE template which interfaces to the picoBus in the usual way using signals but which is also "connected" to a Unix file. The advantage of this method is that the same user's code can be used whether the system is running as a simulation or on hardware. The FileIO AE has two different implementations, one for simulation and one for hardware. In a simulation the connection to the file is simple, since the simulation simply consists of a piece of compiled C++. In hardware, the memory of the AE is used to buffer the data and when required the AE requests the debugger to either empty its memory (for an output FileIO) or fill it (for an input FileIO).

Probe Probe @x @y @x @y

Probes

Probes are special purpose processes inserted into the user's design by utilising unused processors. Probes can be connected to one or more signals, and can non-intrusively monitor all traffic which passes over the signals, as shown in figure 4. They do this by using the bus interconnect's ability to create 1-to-many connections. For example, suppose two processes in a system were connected by a 1-to-1 signal. If a probe is inserted during debugging to monitor that signal, the debug tools will change the 1-to-1 signal into a 1-to-many signal, with the probe acting as an extra destination. The original processes are unaffected by this change (both in terms of latency and bandwidth), but the probe is now able to monitor all communication over that signal.

Probes are implemented as processes, and so can run at full hardware speed. This enables probes to be used to debug systems in real-time. One use for probes is to allow real-time signal traces to be performed. Other uses include signal assertions, and on-chip analysis of data being processed.

Signal assertion probes can be used to check that the data passing over a signal conforms to some compile-time specified property. For example, all signals in picoArray devices have pre-allocated bandwidth. A signal assertion probe could be attached to a signal to record the bandwidth actually used, thus allowing signals with over-allocated bandwidth to be detected.

Probes can be used to perform on-chip analysis of signal data, rather than having to transport the data off-chip (e.g., using traces) for later analysis. For example, during the development of an in-house base station, a probe was created which performed Bit-Error Rate (BER) computation on signals. These BER probes could be used to monitor the performance of the base station's Viterbi decoder's in real-time, under different system loads.

A Method for Design and Debug

This section describes a typical process for creating a pi-coArray based application.

System Decomposition

Typically, this is done by hierarchically breaking down the problem into components consisting of processes connected by signals. Experience has shown that components generally contain a few tens of processes, however the number of processes required does not have to be specified at this stage. The boundaries of these components will also have signals defined and will eventually be connected to other parts of the system. Knowledge of the real-time system being developed is used to specify signal properties, such as maximum bandwidth and signal type. The properties can be checked during integration using signal assertions, which are described in section 4.3.

Component Coding

Two approaches can be taken, the choice being dictated by the complexity of the component.

For small components in which the division into AEs can be determined easily these AEs can be coded using C or assembler and connected using appropriate signals.

For larger components it may be preferable to initially produce a functional representation using C. This can be simulated even when the code size exceeds the memory for any AE, and allows functional testing of this component prior to its division into individual AEs.

Whichever approach is used the code can be tested by creating test harnesses using FileIO (see section 3.5) to mimic the external components. The symbolic debugger and its attendant tools can be used to find bugs within the AEs.

The migration of the code to hardware is eased by the fact that the same FileIO test harnesses produced for simulation can be used for verification. This highlights a huge advantage of this approach, since testing on hardware can be performed at a very early stage. This means that components can be tested for minutes or hours of real time, which would be impossible using simulation.

Small Scale Integration

As components are completed they can be integrated. The strong typing, bandwidth allocation, and fixed process creation ensure that components developed by different people will fit together properly. Signal assertions can be written to encode properties (such as signal value or minimum throughput) of the signals, and these can be checked during integration using assertion probes.

If integration fails (components fail to communicate properly), then this is caused by problems between components, rather than within a component (since the component has been verified in isolation, has static processes, fixed local signals, etc.). The suite of system-wide tools (probes, design browser, etc.) can be used to identify the problem.

Large Scale Integration and Testing

This phase of development can only really be done on the hardware. At this stage all of the FileIO will have been replaced by real components.

It is important to be able to monitor aspects of performance in real-time and this can be done using customised probes which monitor various signals and compare data throughput against predetermined limits. In addition, it is possible to monitor the behaviour of the system when processing real-world data, and to inject data by using the EPI. The results of the monitoring can be displayed using custom GUI's which the user can easily develop.

Comparison with Traditional Techniques

The power of the overall approach described here is that once a component has been written and tested, it can be assumed to work from that point on. Other parallel systems can behave like this for individual components, but then fail to work during integration or, even worse, during customer use. Possible integration problems include:

• priority inversion (e.g., Mars Pathfinder [START_REF] Jones | What really happened on Mars?[END_REF]).

• rogue processes corrupting shared memory

• overflowing message queues

• scheduling failures (e.g., improperly bounded or excessively large critical sections).

• multi-processor bus contention causing nondeterministic communication delays

• incoherency of multi-processor caches Some or all of these problems will afflict other types of parallel systems, from multi-threaded programs containing just two processes through to large scale multi-processors. These problems are difficult to track down because they defy logical analysis, may behave non-deterministically, may only fail very infrequently, or may disappear when debug code is inserted to find the problem. Even if the cause of the problem is found, it is often difficult to write verification to prevent the bug recurring, because of the need to verify the entire system, not just the component or interface which causes the problem. In the worst case, verification may not be possible because it is not apparent why a fix actually works! This solution avoids these types of problem in integration. Individual components which have been properly verified in isolation will behave in the same way when integrated into a complete system. The system behaves deter-ministically, so if problems are found, they can be reproduced, isolated, fixed, and verified. The overall development of systems is more predictable (timescales, etc.), since development isn't held up by strange problems which can't be found until integration.

Conclusion

In order to address its target markets in wireless communications, a family of code compatible devices has been created (currently PC101 and PC102) using the picoArray concept that provides the large computation power required by these applications. To ensure the largest possible computational resource, and recognising that system-wide debug is a major problem in multi-processor designs, a rethink of how to apply debugging was necessary. Therefore it was necessary to shift the debug burden from the hardware to the extensible software tools. The tools provide a way of debugging both single processors and more importantly the large multiprocessor systems possible on a picoArray, or indeed an array of picoArray devices. Experience has shown that using these tools it is possible to construct large working systems (currently in excess of 1000 processors).

  2 322 processors x 2 buses x 32-bits x 160MHz clock

Figure 3 .

 3 Figure 3. Design browser strongly connected component display

Figure 4 .

 4 Figure 4. Probe insertion

Boards with up to 16 devices have been produced. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $

20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)