redactor conf. dr. ing. dorina isar prof. dr. ing. traian jurc · conf. dr. ing. dorina isar prof....

47

Upload: hoangnguyet

Post on 01-Nov-2018

264 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar
Page 2: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Redactor şef / Editor in chief Prof.dr.ing. Ioan Naforniţă Colegiul de redacţie / Editorial Board:

Prof. dr. ing. Virgil Tiponuţ Prof. dr. ing. Alexandru Isar

Conf. dr. ing. Dan Lacrămă Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă

Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar de redacţie Colectivul de recenzare / Advisory Board:

Prof. dr. ing. Miranda Naforniţă, UP Timişoara Prof. dr. ing. Monica Borda, UT Cluj-Napoca Prof. Laurent Toutain, ENST – Bretagne Ing. drd. Simon Csaba, TU Budapest Prof. dr. ing. Virgil Tiponuţ, UP Timişoara Prof. dr. ing. Alimpie Ignea, UP Timişoara Prof. dr. ing. Alexandru Isar, UP Timişoara Prof. dr. ing. Liviu Toma, UP Timişoara Prof. dr. ing. Ioan Naforniţă, UP Timişoara

Page 3: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific

al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ ŞI TELECOMUNICAŢII

TRANSACTIONS ON ELECTRONICS AND COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

SUMAR

ELECTRONICĂ APLICATĂ

Titu Botoş: "Emulating the Attractive Potential Fields with Neural Networks "… … .3

INSTRUMENTAŢIE

Daniel Belega: "Accurate Measurement of RMS Value of a Sinewave in the Case of Noncoherent Sampling"…………………… ... ... ... ... ... ... ... ... … … … … … ..7

Daniel Belega: "True RMS Converter Implemented With TMS320C5X DSK Board"…………………… ... ... ... ... ... ... ... ... … … … … … … … … … … … .11

TELECOMUNICAŢII

Ioan Cleju: "Some New Polynomial Unequal Error Protection Codes"……… … … 15 Florin Dărăban: "A Wei’s Type Multidimensional TCM Encoder"… … … … … … … …21

1

Page 4: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Florin Dărăban: " A Wei’s Type Multidimensional TCM Decoder "… … … … ... … … ..31 Corina Botoca, Georgeta Budura: "Competitive Neural Network for Congestion Control"… … … … … ...37 Florin Vancea, Codruţa Vancea: "Propagarea identificatorilor de securitate în apeluri EJB efectuate din container de servlet cu implementare Single-Sign-On"… … … … … … … …41

2

Page 5: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

1as. ing. T. Botoş Address: Universitatea “Politehnica” Timişoara Bd. V. Pârvan nr.2 1900 Timişoara, Romania; Email: [email protected];

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

Emulating the attractive potential fields with neural networks

Titu Botoş1

Abstract - A way to implement the attractive field component of a potential field guidance principle with neural networks is presented in this paper. Two possible implementations are analyzed and compared, one with a feedforward and another with a competitive network.

I. INTRODUCTION

From the multitude of guidance methods for mobile robots know nowadays, the potential field approach has its one distinct place, due to its efficiency. Although it was first designed for on-line mobile robot guidance, it finds itself at the border between local and global path planing algorithms. The potential field guidance method could be applied if only momentary sensorial information is available or if an environmental map is known.

As its name shows the method uses potential fields to control the mobile robot trajectory. The robot is considered to be a charged particle under the field influence. By associating an attractive potential field to the target and repulsive fields to obstacles, a path toward the target is generated if the negative gradient of the potential field is followed [4].

Despite of its efficiency and large practical applicability this method has to deal with local minimums that represents its main drawback. These local minimums could interfere and prevent reaching the target for particular geometry of the mobile robot environment. This is the reason why the research in the field is trying to find a navigation function that will provide a potential field with a single minimum (the target) [1] [2] [3].

Potential field guidance principle could be emulated with neural networks. The solution presented in [5] makes use of two neural networks, one for each potential field component.

In this paper the way of implementing the attractive field with neural networks is analyzed. The previous implementation presented in [5] shows that the answer of the neural network that emulates the attractive filed become uncertain in the vicinity of the target. With the present study we try to overcome this weakness.

The paper is organized as follows: section II introduces the feedforward solution; section III proposes an implementation with a competitive network; and the conclusions are the subject of section IV.

II. ATTRACTIVE FIELD EMULATION WITH FEEDFORWARD NETWORKS

To emulate the behavior of the attractive

field, the neural network has to offer at its output the direction that should be followed in order to reach the target, for each point from the mobile robot workspace supplied at its input.

In order to build the neural network training database, the bidimensional space shown in figure 1 was uniformly divided. The Cartesian coordinates of the intersection points of the rectangular grid constituted the training models for the network (so, the network has 2 inputs). For each of them an appropriate direction was defined, being the associate-model in the training database (in figure 1 these direction are suggested with small arrows). Four main directions were chosen (N, E, S, W) and for each of them an output neuron was designated.

The target was placed in the middle of the workspace (the point with (0; 0) coordinates), and any point in the workspace could be chosen as a start point.

3

Page 6: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Figure 1. Traveling direction distribution.

During the training phase it was proved that the emulation of the field by the neural network is greatly improved if the grid is smaller. The training database was constructed using a 20 by 20 grid, figure 1 suggests only the idea. Multiple tests were shown that 14 neurons in the hidden layer are the best choice. The optimum network has a 4 input - 14 hidden – 4 output neurons structure, all of them with sigmoidally transfer function.

The network answer for 400 uniform spread test vectors is shown in figure 2. Here a plot is depicted for each of the four output neurons. It is not hard to see that the workspace was divided among the four neurons in four zones. This behavior was predicted by the chosen direction in figure 1. The firing level of the neurons is direct proportional with the blackness of the plot.

By controlling the trajectory of an holonomous mobile robot in an obstacle free environment with such a network, a trajectory like one in figure 3 is obtained. The start point was chosen to be (-0.5; -1), but the behavior of the network is similar for any start point in the workspace.

The firing level for the "S" neuron along this trajectory is depicted in figure 4. As one can see, the firing level tends to minimize its value as soon as the mobile gets closer to the target. The same thing could be observed if figure 2 is more closely analyzed.

Along the border between to adjacent zones the firing level is lower, shown in gray. The same effect could be seen in figure 4 between the iteration 50 and 100, that corresponds to the diagonal segment of the trajectory in figure 3. Because of the attenuation of the network answer in the vicinity of the target a post-processing algorithm is required. In order to decide among the four possible traveling directions, the output neuron with the highest firing level has to be found. Despite of the fact that this proceeding gives good results (as the example in figure 3 proves) it is however inappropriate to use it in conjunction with neural algorithms. The flattened neural network answer in the vicinity of the target is due to the stabilization feature of the potential attractive field. The attractive

component has to create a stable equilibrium zone around the target, in order to "trap" the mobile robot.

Figure 2. The workspace divided among the 4 output neurons

Figure 3. The followed trajectory under the feedforward network

control.

Figure 4. Firing level of neuron "S" along the trajectory presented

in figure 3. To emulate this behavior the target point has been added in the training database with a null answer for the output neurons. Once the target has been reached

4

Page 7: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

the neural network must keep the mobile there. Although this is the desired behavior, the undecided network answer near the target is regarded as a drawback of the feedforward approach.

III. ATTRACTIVE FIELD EMULATION WITH COMPETITIVE NETWORKS

Another possible approach for attractive field

emulation with a neural network is to make use of a competitive one. With this type of network, the drawback of the flattened answer around the target is overcame, due to the competitive output layer that provides an "all-or-nothing" type answer. This way the post-processing phase that decides the next traveling direction, used in the previous case is eliminated.

The Cartesian coordinates of the current point in which the mobile robot resides are the network inputs as in the previous case. The competitive network has two inputs, but this time, the network output will represent the zone to which the input point belongs. The workspace is now divided in distinct convex zones among the output neurons.

Theoretically the number of the neurons in the output layer is unlimited. As this number grows the shape of the basin of the emulated attractive field will be closer to a cone shape and the trajectory followed by the mobile to the target will be shorter. But a higher number of output neurons (>12) increases the network complexity without providing better quality. At the same time the minimum number of the neurons in the output layer must be four.

The weights of the output neurons could be determined following two different ways. First, one can try to train such a network with uniform training vectors spread over the workspace. Second, the weights could be calculated due to a prior knowledge of the problem. From now a symmetrical arrangement of the output neurons is considered, as in figure 5 (the neurons are marked as four small crosshairs).

Finally another neuron has to be added, the central neuron "C". This neuron is placed at the target position, with a very small basin. This is done by setting the weights for this neuron to (0; 0) pair, and by choosing for its bias a high value. The bias value has to be high because it determines the width of the equilibrium zone. This latest neuron will be fired only when the mobile reaches the target and it will provide the stabilization feature of the emulated attractive field.

The attractive basins and the arrangement of the output neurons for a four-output and eight-output competitive network type are depicted in figure 5 and respectively in figure 6.

If the test that give us the results shown in figure 2 were made again for the competitive network, only black and white zones without intermediary gray levels will be obtained.

Being tested in the same condition as the feedforward network was (see figure 3), the competitive network with 5 output neurons gives the trajectory from figure 7.

Figure 5. The workspace divided among the 4 output

neurons for a competitive network. Figure 6. The workspace divided among the 8 output neurons for a

competitive network.

Figure 7. The followed trajectory under the competitive network control.

By comparing the trajectories depicted in

figure 3 and 7, one may see that the results are identical, but with a competitive layer providing an undoubted answer the post-processing algorithm needed previously is eliminated.

Based on the clear answer of the competitive layer, a new controlling feedforward network could be developed. This new network will provide the

5

Page 8: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

necessary position increment that has to be added to the present coordinates in order to reach the target.

The structure of this controlling layer is depicted in figure 8, here the weights with zero value are not shown.

Figure 8. The controlling feedforward network.

The two neurons from the output layer of the

network in figure 8 have a linear transfer function. The weights were chosen in such a way that the outputs provides either -1, 0 or 1 values, and for each iteration one step toward the target is made. For competitive networks with more than 5 outputs, the weights of the supervising network could be designed in such a manner that both its outputs cold be fired at the same time and so a diagonal movement can be achieved. With the arrangement shown in figure 8, the movement takes place only on one of the two directions at once.

IV. CONCLUSIONS

In this paper two implementing ways for emulating the potential attractive field with neural networks were presented one with a feedforward network and the other with a competitive layer. Comparison of their behavior and the obtained results were made.

The reason way the feedforward network answers is "flattened" in the vicinity of the target was explained, and from this point of view the advantage of the competitive layer was stressed.

Both networks have a good generalization capability, providing appropriate answers for vectors that were not in the training database.

Choosing the competitive network variant, a smaller network was obtained. Instead of the 2 - 14 - 4 arrangement for the feedforward network, the size can be cut down to a 2 - 5 structure for a competitive layer.

The target point coordinates were chosen to be (0; 0). This assumption does not mean a restriction, because any other combination of the target and the start points could be reduce to the present one by simple subtracting their coordinates.

By choosing the competitive network to emulate the attractive field, the advantage of its clear answer can be taken and a supervising network layer to compute the position increment can be added.

References [1] J Guldnen, V.I.Utkin Sliding mode control for gradient

tracking and robot navigation using artificial potential fields. IEEE Transaction on Robotics and Automation Apr.1995.

[2] Y.K.Hwang, N.Ahuja A potential field approach to path planning. IEEE Transaction on Robotics and Automation Feb.1992.

[3] E.Rimon, D.E.Koditschek Exact robot navigationusing artificial potential functions. IEEE Transaction on Robotics and Automation Oct.1992.

[4] S.Sundar, Z.Schiller Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman Equation. IEEE Transaction on Robotics and Automation Apr.1997.

[5] T.Botos, V.Tiponuţ Artificial potential field navigation with neural networks for a mobile robot. Sesiunea de comunicări Hunedoara 4-5 Nov. 1999.

IncrementY

N S C V E

-1 1 1 -1

IncrementX

1

6

Page 9: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

Accurate Measurement of RMS Value of a Sinewave in the Case of Noncoherent Sampling

Daniel Belega 1

1 Faculty of Electronics and Telecommunications, Dept. of Measurements and Optical Electronics, e-mail: [email protected]

Abstract – Based on the formula used for calculating the root mean square (rms) value of a discrete-time signal is derived an expression for the rms value of a sinewave in the case of noncoherent sampling. The results obtained by simulation confirm the accuracy of this expression. From the expression obtained are deduced some important conclusions concerning the accuracy in the measurement of the rms value of a sinewave. Index terms: calculation of rms value of a sinewave, noncoherent sampling.

I. INTRODUCTION One of the most important parameters of a signal is its rms value because this is a measure of the signal power. For a discrete-time signal x(n), n=0, 1, 2,…, N-1 the rms value is given by the formula

( ) 21

0

21

0

2 )(1)(1 xnxN

xnxN

XN

n

N

nrms −=−= ∑∑

=

=

(1)

where x is the mean value of the signal x(n); x is given by

∑−

=

=1

0

.)(1 N

n

nxN

x

(2)

The signal x(n) is obtained by means of a digitizing waveform recorder. In practical applications often the sampling frequency of the digitizing waveform is not synchronized to the fundamental frequency of the x(n) (noncoherent sampling) [1]. In this paper is analyzed the influence of the noncoherent sampling on the rms value of a sinewave calculated by the formula (1). It is derived an expression for the rms value of a sinewave in the case of noncoherent sampling. The accuracy of this expression is verified by means of computer simulation. The expression obtained leads to important conclusions concerning the precision in the measurement of the rms value of a sinewave.

II. CALCULATION OF RMS VALUE OF A SINEWAVE

Consider a sampled sinewave of amplitude A, frequency fin, initial phase ϕ0 and offset d, defined by

1,...,2,1,0,2sin)( 0 −=+⎟⎟⎠

⎞⎜⎜⎝

⎛ϕ+π= Nndn

ffAnx

s

in

(3)

where fs is the sampling frequency and N is a number of samples. Consider that the sampling process is noncoherent with the sinewave. Thus, the relationship between the frequencies fin and fs is

NNJ

NJ

ff

s

in δ+=

δ+= (4)

where J is the number of sinewave cycles (J is an integer) and 0 < δ <1. The rms value of the signal x(n) is determined in Appendix as

errAX rms2

≅ (5)

where

,)(

)(sin)(sin2

)(2)22cos()2sin(1

220

22

0

δ+πϕ+πδπδ

δ+πϕ+πδπδ

−=

J

Jerr

(6)

with the condition

.10 ins ff π≥ (7) In the case of coherent sampling, i.e. δ = 0 in (4), results from (5), as we expected, that the rms value is equal with the ideal rms value 2/AX idealrms = (err = 1).

7

Page 10: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

The accuracy of the expression (5) is verified by means of computer simulation. The signal x(n) used in simulation was characterized by A = 1 and d = 0.1. The number of sinewave cycles was J = 8. The verification was made in two situations: 1) δ and N variables and ϕ0 = 300. Fig. 1 shows the absolute value of the maximum difference between the simulated and the calculated rms values obtained during δ scan as a function of N. δ scan was made in (0,1) with an increment step of 0.01.

Fig. 1. The absolute value of the maximum difference between the simulated and the calculated rms values

obtained for δ∈(0,1) as a function of N. From Fig. 1 results that the difference between the simulated and the calculated rms values decreases as N increases. For N ≥ 300 the absolute values of the maximum differences are smaller than 10-3 and for N ≥ 2900 are smaller than 10-4. Fig. 2 shows the simulated and the calculated rms values as a function of δ for N = 1200.

Fig. 2. The simulated and the calculated rms values as

a function of δ. 2) ϕ0 and N variables and δ = 0.2. Fig. 3 presents the absolute value of the maximum difference between the simulated and the calculated rms values obtained during ϕ0 scan as a function of N. ϕ0 scan was made in (00, 3600) with an increment step of 3.60.

Fig. 3. The absolute value of the maximum difference between the simulated and the calculated rms values

obtained for ϕ0∈(00,3600) as a function of N. From Fig. 3 results that the calculated rms value is more closely to the simulated rms value as N increases. For N ≥ 400 the absolute values of the maximum differences are smaller than 10-3 and for N ≥ 3300 are smaller than 10-4. Fig. 4 presents the simulated and the calculated rms values as a function of ϕ0 for N = 1200.

Fig. 4. The simulated and the calculated rms values as

a function of ϕ0. Both analyzed situations confirm that the expression derived is very accurate for N ≥ 10π (J+δ) (i.e. for fs ≥ 10πfin). From the expression (5) results the following important conclusions: • for small J the rms value depends on δ and ϕ0 values. Fig. 5 shows the relative error of the rms value as a function of δ and ϕ0 for N = 1200. The relative error is defined by

.[%]100.idealrms

idealrmsrms

XXX

errorrel−

= (8)

8

Page 11: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Fig. 5. The relative error of the rms value as a

function of δ and ϕ0. • for high J the relative error of the rms value is very small and so, the rms value is very accurate measured. In this case err can be approximated by

.2

)22cos()2sin(1 0

Jerr

πϕ+πδπδ

−≅ (9)

In the most worst situation (i.e. sin(2πδ)cos(2πδ+2ϕ0) = 1, which implies δ = 0.25 or 0.75 and ϕ0 = 1350) the maximum value for err is given by

.2

11max Jerr

π−= (10)

For example, when J ≥ 160, in the worst situation the relative error is smaller than 0.05%.

III. CONCLUSION In this paper the influence of the noncoherent sampling on the rms value of a discrete-time sinewave calculated by the classical formula has been investigated. It is derived an expression for the sinewave rms value in the case of noncoherent sampling. The expression is very accurate when the sampling frequency is 10π times higher than the sinewave frequency. The most important conclusion deduced from the expression derived is that the rms value of a sinewave, in the case of noncoherent sampling, can be very accurate measured when the number of sinewave cycles is high.

APPENDIX From (1) results

21

0

22 )(1 xnxN

XN

nrms −= ∑

=

(A.1)

where

.)(1 1

0∑−

=

=N

n

nxN

x (A.2)

Consider the sinewave given by (3), acquired under the noncoherent sampling. The relationship between the sampling frequency fs and the sinewave frequency fin is given by (4). For the calculation of the rms value of the signal x(n) were used the following identities [2]:

⎟⎠

⎞⎜⎝

⎛ −+θ

⎟⎠

⎞⎜⎝

⎟⎠⎞

⎜⎝⎛

=

−+θ+++θ+θ

hnh

nhhnh

21cos

2sin

2sin

))1(cos(...)cos(cos

(A.3)

.2

1sin

2sin

2sin

))1(sin(...)sin(sin

⎟⎠

⎞⎜⎝

⎛ −+θ

⎟⎠

⎞⎜⎝

⎟⎠⎞

⎜⎝⎛

=

−+θ+++θ+θ

hnh

nhhnh

(A.4)

By using (A.4) the mean value of the signal x(n) is given by

( ) ( ) ( ).

sin

1sinsin1

2sin1

0

1

00

d

NJ

JN

N

NA

dnN

JAN

x

J

N

n

+⎟⎠

⎞⎜⎝

⎛ δ+π

⎟⎠

⎞⎜⎝

⎛ ϕ+δ+π−

πδ−=

⎟⎟⎠

⎞⎜⎜⎝

⎛+⎟

⎞⎜⎝

⎛ ϕ+δ+

π= ∑−

=

(A.5)

For the values of N used in practice

.11≅

−N

N (A.6)

Assuming

1<<δ+

πN

J (A.7)

results

.sinN

JN

J δ+π≅⎟

⎠⎞

⎜⎝⎛ δ+π

(A.8)

Thus, from (A.6) and (A.8) we have

( ) ( ) ( ) .sinsin10 d

JAx +ϕ+πδπδ

δ+π≅

(A.9) The sum of the square of the samples of x(n) is given by

9

Page 12: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

.2sin2

2sin)(

1

00

2

1

00

221

0

2

∑∑−

=

=

=

⎟⎠

⎞⎜⎝

⎛ ϕ+δ+

π++

⎟⎠⎞

⎜⎝⎛ ϕ+

δ+π=

N

n

N

n

N

n

nN

JAdNd

nN

JAnx

(A.10)

By using (A.3) we have

( ) ( ).

2sin

221cos2sin

2

22

24cos1

2sin

02

201

0

2

1

00

22

⎟⎠⎞

⎜⎝⎛ δ+π

⎟⎠⎞

⎜⎝⎛ ϕ+δ+π

−πδ

=⎟⎠⎞

⎜⎝⎛ ϕ+

δ+π−

=

⎟⎠⎞

⎜⎝⎛ ϕ+

δ+π

=

=

NJ

JN

NA

ANn

NJ

A

nN

JA

N

n

N

n

(A.11)

From (A.6) and (A.8) results

( ) ( )( ) .

222cos2sin

2

22sin

02

1

0

2

022

δ+πϕ+πδπδ

≅⎟⎠⎞

⎜⎝⎛ ϕ+

δ+π∑

=

JAN

ANnN

JAN

n

(A.12)

By using (A.4) and (A.12) the expression (A.10) becomes

( ) ( )( )

( ) ( )( ) .sinsin22

22cos2sin2

2)(

0

202

21

0

2

δ+πϕ+πδπδ

+

+δ+π

ϕ+πδπδ−

≅∑−

=

JdNA

NdJ

AN

ANnxN

n

(A.13)

From (A.9) and (A.13) the expression (A.1) becomes

( ) ( )( )

( ) ( )( )

.sinsin22

222cos2sin1

2

220

222

02

2

⎟⎟⎠

⎞⎜⎜⎝

δ+πϕ+πδπδ

⎟⎟⎠

⎞⎜⎜⎝

⎛δ+π

ϕ+πδπδ−≅

JA

JAX rms

(A.14)

The expression (A.14) can be written as

errAX rms2

≅ (A.15)

where

( ) ( )( )

( ) ( )( )

.sinsin2

222cos2sin1

220

22

0

δ+πϕ+πδπδ

δ+πϕ+πδπδ

−=

J

Jerr

(A.16)

The condition (A.7) implies

( )δ+π≥ JN 10 (A.17) or, equivalently, from (4)

.10 ins ff π≥ (A.18)

REFERENCES

[1] O. M. Solomon, ”The Use of DFT Windows in Signal-to-Noise Ratio and Harmonic Distortion Computations,” IEEE Trans. Instrum. Meas., vol. 43, pp. 194-199, April 1994.

[2] Gh. Sireţchi, Calcul diferenţial şi integral, Editura Ştiinţifică şi Enciclopedică, Bucureşti, 1985, vol. 2, pp. 573.

10

Page 13: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

x(t) x(n) Xrms

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

True RMS Converter Implemented With TMS320C5X DSK Board

Daniel Belega 1

1 Faculty of Electronics and Telecommunications, Dept. of Measurements and Optical Electronics, e-mail: [email protected]

Abstract - The paper propose a practical true rms converter implemented with the TMS320C5X Starter Kit (DSK) board. Experimental results illustrating the performances of this converter in the case of a sinusoidal signal are also included. Index terms: true rms value computation, coherent sampling, digital signal processor.

I. INTRODUCTION The true root mean square (rms) value is one of the most useful parameter of a periodic signal since it relates directly to the power of the signal. When an analog signal x(t) of frequency fin is discretized by means of a digitizing waveform recorder is obtained the discrete-time signal x(n), n = 0, 1,…, N-1. The true rms value of the signal x(n) is

( )∑−

=

=1

0

21 N

nrms nx

NX

(1)

From (1) results that the direct computation of true rms value of the signal x(n) involves three operations: square, sum and square root (Fig. 1).

Fig. 1. The block diagram for direct computing the true rms value of the signal x(n).

The true rms value of the signal x(n) is very accurate estimated by Xrms when the samples were acquired under coherent sampling condition [1]:

NJ

ff

s

in = (2)

where fs is the sampling frequency of the digitizer waveform; J is the number of the signal cycles (J is an integer). In this paper a practical true rms converter implemented by means of the TMS320C5X Starter Kit (DSK) board [2] is proposed. The true rms value was computed by formula (1). The samples used to compute the true rms value were acquired under synchronous sampling condition (2). Moreover, based on the experimental results was investigated the accuracy of this converter in the estimation of the true rms value of a sinewave.

II. THE TRUE RMS CONVERTER The true rms converter was implemented with the TMS320C5X DSK board. The DSK is a low-cost, simple, stand-alone application board equipped with a 16-bit fixed-point digital signal processor (DSP) - TMS320C50 [3]. This board allows implementation of real-time signal processing applications with TMS320C50 DSP. For this purpose the DSK contain an analog interface circuit (AIC) TLC32040, which provides the necessary conversion between the analogue and digital domain. For this purpose it incorporates a band-pass antialiasing input filter, a 14-bit analog-to-digital converter (ADC), a serial port by which AIC communicate with TMS320C50 DSP, a 14-bit digital-to-analog converter (DAC) and a low- pass output reconstruction filter. DSK is connected to a PC via a RS232C interface. By means of the DSP were implemented all three operations involved in the computation of the true rms value (see Fig. 1). Based on the experimental results is analyzed the accuracy of the converter proposed in the case of particular signal type – sinusoidal signal. The

ADC X2 ∑

TMS320C50 DSP

11

Page 14: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

programmable function generator HM8130 was used to generate the sinewaves. For DSK were made the following settings: sampling frequency fs = 48.077kHz, the gain of the preamplifier is 2 (for which the full-scale range (FSR) of the ADC of the AIC is 6V) and without the input band-pass filter of the AIC. The offset of the sinewaves was 0V. The input frequencies of the sinewaves was chosen to satisfy the coherent sampling condition (2) with J = 1. The program for computing the true rms value was written in the DSK assembly language. In Appendix is presented the program written for N = 32. For the converter was, also, written in Matlab 4.2 a graphical interface. This interface presents the signal acquired (used to compute the true rms value) and the true rms value computed. The accuracy in computing the true rms value was appreciated by means of the relative error, defined by:

[%]100.idealrms

idealrmsrms

XXX

errorrel−

=

(3)

where 2

AmpX idealrms = , Amp is the amplitude of the

sinewave estimated by the Interpolated Fast Fourier transform (Interpolated FFT) algorithm [4]. This algorithm provides very accurate amplitude estimates. In the Interpolated FFT algorithm were used 1024 samples and the 4–term maximum decay window. Fig. 2 illustrates the performances of the converter as a function of N. The amplitudes of the sinewaves were A = 3V, equals with half of FSR of the ADC (correspond to the maximum value represented on 16 bits (7FFFhexa)).

Fig. 2. The absolute value of the relative error

as a function of N.

From the performances shown in Fig. 2 results that the true rms value is very accurate estimated for 9 ≤ N ≤ 16 and accurate estimated for 16 < N ≤ 128. Fig. 3 presents the graphical interface for N = 16 (Fig. 3a) and N = 96 (Fig. 3b).

(a)

(b)

Fig. 3. The graphical pages in the cases: (a) N = 16 and (b) N = 96.

Fig. 4 shows the precision in computing the true rms value as a function of the amplitude of the sinewave. Was used N = 16.

Fig. 4. The absolute value of the relative error as a function of the amplitude of the sinewave.

Fig. 4 show that the performances in estimating the true rms value increases when the amplitude decreases. This behavior is caused by the operation with fixed-point arithmetic. This operation type introduces constant errors in absolute value and, so led to an increases of relative errors when the sample values decreases [5]. From Fig. 4 results also, that the true rms value is very accurate measured for 2A ≥ FSR/2 and accurate measured for FSR/3 ≤ 2A < FSR/2.

12

Page 15: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

III. CONCLUSION In this paper is proposed a practical true rms converter implemented with TMS320C5X DSK board. The advantages of computing the true rms value of a periodic signal by means the DSK board are: higher flexibility in programming, very accurate measurement and real-time computation. From the measurements effected in the case of sinusoidal signal results that the true rms value of a sinewave is accurate estimated when the number of samples is small and the peak-to-peak amplitude of the sinewave is higher than one third of the FSR of the ADC.

APPENDIX Below is presented the program which compute the true rms value of a periodic signal by means of N = 32 samples.

.mmregs

;===============================================; ;= SETTINGS =; ;===============================================; TA .set 8 ; Set the sampling frequency to 48.077kHz RA .set 8 TB .set 13 RB .set 13 AIC_CTR .set 24 ; | xx G1 G0 | SY AX LB BP| ; +------------+-----------------+ ; | GAIN | | |+-- BP Filter ; | Synch --+ |+----- Loopback ; | Auxin --------+ begin .set 3072 ; Set the start address up to which are stored

; the samples acquired N .set 32 ; Set the number of samples used to

; compute the true root mean square value offset .set 20 ; Set the number of samples acquired which ; are ignored to obtain an accurate signal

; acquired N1 .set 1024 ; Set the number 1/N in Q15 format .ds 0f00h ; Assemble to data memory contor1 .word 0 ; (contor1) is a counter for the samples

; used to compute the true root mean ; square value

contor2 .word 0 ; (contor2) is a counter for the samples ; acquired pas .word 0 ; Location for a variable used in SQRT

; subroutine x0 .word 0 ; Location for the current sample sum .word 0 ; Location for the sum rms .word 0 ; Location for the root mean square value ;===============================================; ;= INTERRUPT SETTINGS =; ;===============================================; .ps 080ah ; Assemble to program memory RINT b RX ; Branch to RX on receive interrupt XINT b TX ; Branch to TX on transmit interrupt ;===============================================; ;= PROCESSOR INITIALISATION =; ;===============================================; .ps 0a00h ; Assemble to program memory .entry ; Mark program entry point .text ; Text START setc INTM ; Disable interrupts

ldp #0 ; Set data page pointer to page zero splk #0834h,PMST ; Write 16 bit pattern to ; PMST register lacc #0 ; Load ACC with zero

samm CWSR ; Set software wait state to zero samm PDWSR ; Set software wait state to zero splk #022h,IMR ; Using XINT syn TX & RX call AIC ; Initialize AIC and enable ; interrupts ;----------------------------------------; lar AR0,#begin ; AR0 = begin

lacc #offset ; ACC = offset ldp #contor1 ; Load data page contor1 sacl contor1 ; (contor1) = offset lacc #N ; ACC = N sacl contor2 ; (contor2) = N lacc #0 ; ACC = 0 sacl sum ; (sum) = 0 ldp #0 ; Set data page pointer to page zero ;---------------------------------------; clrc OVM ; Overflow mode is set to zero spm 0 ; Product shift mode is set to zero splk #012h,IMR ; Mask interrupts clrc INTM ; Enable interrupts ;===============================================; ;= MAIN PROGRAM =; ;===============================================; WAIT ldp #contor1 ; Load data page contor1 lacc contor1 ; ACC = (contor1) bcnd WAIT,gt ; Branch to WAIT until ; (contor1) ≤ 0 lacc contor2 ; ACC = (contor2) bcnd WAIT,gt ; Branch to WAIT until ; (contor2) ≤ 0 ldp #0 ; Set data page pointer to page zero setc INTM ; Disable interrupts

splk #02h,IMR ; Mask interrupt INT2 splk #10h,TCR ; Stop the timer nop ; No operation nop ; No operation clrc INTM ; Enable interrupts call SQRT ; Call subroutine SQRT STOP b STOP ; Branch to STOP ;===============================================; ;= RECEIVE INTERRUPT SERVICE ROUTINE =; ;===============================================; RX ldp #contor1 ; Load data page contor1 lacc contor1 ; ACC = (contor1) sub #1 ; ACC = (contor1) - 1 sacl contor1 ; (contor1) = (contor1) - 1 bcnd et,geq ; Branch to et until (contor1) < 0 ldp #contor2 ; Load data page contor2 lacc contor2 ; ACC = (contor2) sub #1 ; ACC = (contor2) - 1 sacl contor2 ; (contor2) = (contor2) - 1 zap ; ACC = PREG = 0 lamm DRR ; Read data from DRR and #0fffch ; Clear lower two (status) bit

; from ACC mar *,AR0 ; AR0 becomes the current

; auxiliary register sacl *+ ; ((AR0)) = ACC, AR0 = AR0 + 1

ldp #x0 ; Load data page x0 sacl x0 ; (x0) = ACC sqra x0 ; Compute the square value spm #0 ; of the current sample xk

2 pac ; and store the result to the abs ; address x0 without sach x0,1 ; the supplementary sign bit lt x0 ; TREG0 = xk

2 mpy #N1 ; PREG = xk

2 * N1 pac ; ACC = PREG sach x0,1 ; Remove the sign bit; store the

; value xk2/N to the address x0

lacc x0 ; ACC = xk2/N

add sum ; ACC = xk2/N + (sum)

sacl sum ; (sum) = xk2/N + (sum)

et nop ; No operation rete ; Return to main program

13

Page 16: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

;===============================================; ;= TRANSMIT INTERRUPT SERVICE ROUTINE =; ;===============================================; TX

rete ; Return to main program ;===============================================; ;= BOARD INITIALISATION =; ;===============================================; AIC

splk #20h,TCR ; To generate 10 MHz from Tout splk #01h,PRD ; Load period counter with 1 mar *,AR0 ; Modify AR pointer

; (used with GREG) lacc #0008h ; Load ACC with 08h sacl SPC ; Store ACC in SPC lacc #00C8h ; Load ACC with 0C8h sacl SPC ; Set and reset SPC register ;---------------------------------------; lacc #080h ; Initialize 8000h to FFFFh as

; global memory sach DXR ; Store high ACC to DXR sacl GREG ; Store to global memory register lar AR0,#0FFFFh ; Set AR0 register rpt #9999 ; Set repeat counter lacc *,0,AR0 ; Access global memory sach GREG ; Disable global memory ;---------------------------------------; setc SXM ; Set SXM for sign extension mode lacc #TA,9 ; Load ACC with TA data add #RA,2 ; Load ACC with RA data call AIC2ND ; Call function AIC2ND ;--------------------------------------; lacc # TB,9 ; Load ACC with TB data add RB,2 ; Load ACC with RB data add #02h ; Add 10b to set status bits call AIC2ND ; Call function AIC2ND ;--------------------------------------; lacc #AIC_CTR,2 ; Initialized control register add #03h ; Add 11b to set status bits call AIC2ND ; Call function AIC2ND ret ; Return from call ;-------------------------------------; AIC2ND

ldp #0 ; Load data page zero sach DXR ; Store upper ACC to DXR clrc INTM ; Enable interrupts idle ; Idle until interrupt - TINT add #6h,15 ; Set 2 LSBs of upper ACC high sach DXR ; Store upper ACC to DXR idle ; Idle until interrupt - TINT sacl DXR ; Store lower ACC to DXR idle ; Idle until interrupt - TINT lacl #0 ; Store lower ACC to DXR - flushing sacl DXR ; make sure the word got sent idle ; Idle until interrupt - TINT setc INTM ; Disable interrupts ret ; Return from call

;===============================================; ;= SQUARE ROOT COMPUTATION SUBROUTINE =; ;===============================================;SQRT ldp #0 ; Load data page zero setc SXM ; Set SXM for sign extension mode spm #1 ; Product shift mode is set to one lacl #0 ; Load lower ACC with zero sacb ; Clear ACC buffer ldp #0 ; Load data page zero splk #11,BRCR ; Initialize for 12 iterations ldp #pas ; Load data page pas splk #8000h,pas ; Set initial guess lacc sum ; ACC = (sum) sub #200h,0 ; ACC = (sum) – 200h

bcndd loop,lt ; If (sum) < 200h then begin looping splk #8000h,rms ; (rms) = 8000h lacc #4000h ; Otherwise set initial guess and sacl pas ; temporary root sacl rms ; to 4000h ldp #0 ; and splk #14,BRCR ; increase iterations to 15 ldp #rms ; Load data page rms loop rptb endlp ; Repeat block sqra rms ; Square temporary root lacc sum,16 ; ACChigh =(sum) spac ; ACC = (sum) – (rms)2

nop ; No operation xc 2,gt ; If (sum) > (rms)2 then skip next ; two instructions lacc rms,16 ; Otherwise sacb ; Root <- (rms) lacc pas,15 sach pas ; (pas) = (pas)/2 addb endlp sach rms ; (rms) = Root + (pas) lacc rms ; Location with the address rms abs ; contain the sacl rms ; true root mean square value mar *,AR0 ; The true root mean square sacl * ; value is stored in the location ; with the address begin + N +1 ret ; Return from call ;-----------------------------------------; .end ; End of program

REFERENCES

[1] A. Ferrero, R. Ottoboni, “A Low-Cost Frequency Multiplier for Synchronous Sampling of Periodic Signals,” IEEE Trans. Instrum. Meas., vol. 41, pp. 203-207, April 1992.

[2] TMS320C5X DSP Starter Kit User’s Guide, Texas Instruments 1994.

[3] TMS320C5X User’s Guide, Texas Instruments 1997. [4] C. Offelli, D. Petri, “Interpolation Techniques for Real-

Time Multifrequency Waveforms Analysis,” IEEE Trans. Instrum. Meas., vol. 39, pp. 106-111, Feb. 1990.

[5] C. Narduzzi, C. Offelli, “Real-Time High Accuracy Measurement of Multifrequency Waveforms,” IEEE Trans. Instrum. Meas., vol. IM-36, pp. 964-970, Dec. 1987.

14

Page 17: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

Some New Polynomial Unequal Error Protection Codes

Ioan I. Cleju1

1 Facultatea de Electronică şi Telecomunicaţii, Departamentul Electronică Aplicată , Bd. Copou Iaşi 6600 e-mail [email protected]

Abstract – In literature, Unequal Error Protection codes (UEP Codes) are described and studied based on parity check or generator matrices. In this paper we present a computational algorithm which provides generator polynomials for cyclic and pseudo-cyclic (polynomial) codes which have UEP properties. We devised several C++ programs and then we realized a complete table with all the polynomial codes with UEP properties having length n # 30 and distances up to 9. Keywords: error-correcting codes, protection level, cyclic code, separation vector

I. INTRODUCTION

This paper combines two different topics : the unequal error protection codes over an arbitrary finite field and the cyclic and pseudo-cyclic codes. In the first part we give the definition for Linear Unequal Error Protection (LUEP) codes. These codes offer a different level protection against errors for different message symbols. They should be used in the message word according to the importance of the symbol , e.g. in the transmission of numerical data where errors in the sign or in the high-order digits are more serious than errors in low-order digits. It is also possible for the protection level to be burst of errors and single bit errors, [1]. On the other hand, the class of cyclic codes are a constant focus of interest to both mathematicians and engineers due to their simplicity and facility of implementing the encoder and decoder circuit. Puncturing a cyclic code, we shall obtain a shortened cyclic code or a pseudo cyclic code, which has at most the same error correcting capability as the starting one. Thus we shall present only the properties of a cyclic code which enable us to understand the way such a code can be an UEP code. We intend to construct cyclic or pseudo-cyclic codes which have two or more levels of protection against random single errors. Finally, we shall present a computational algorithm which can provide the generator polynomial of a Linear Polynomial (cyclic or pseudo-cyclic) Unequal Error Protection (LPUEP) code. Using this algorithm we have devised several

programs in C++ by the help of which we have constructed a complete table with all the LPUEP codes of length less than or equal to 30.

II. THEORETICAL CONSIDERATIONS A. Cyclic and Polynomial Codes Definition 1. An (n,k) linear code C is cyclic if every cyclic shift of a codeword (codevector) is also a codeword (codevector) in the code. A codevector v = [v0,v1, … ,vn-1) of a cyclic code may also be expressed in a polynomial form with indeterminate x

012n

2n1n

1n vxvxvxvv(x) ++++= −−

−− K (1)

v(x) is called the code polynomial of the codevector v . For an (n,k) cyclic code, the code polynomial has a degree of n-1 (if vn-1 ≠ 0). If C is an (n,k) code, then the collection of codewords in C, forms a vector subspace of dimension k within the space of all n-tuples over GF(q). It follows that the code polynomials associated with C also form a vector subspace, this time within GF(q)[x]/(xn – 1). The following theorem, [2], [3], will prove to be extremely useful in characterizing these codes: Theorem 1. Let C be a (n,k) linear cyclic code : 1. Within the set of code polynomials in C there is a

unique monic polynomial g(x) with minimal degree r < n. g(x) is called the generator polynomial of C.

2. Every code polynomial c(x) in C can be expressed uniquely a c(x) = m(x)*g(x), where g(x) is the generator polynomial of degree less than k=(n-r) in GF(q)[x].

3. The generator polynomial g(x) of C is a factor of xn-1 in GF(q)[x].

Since g(x) is monic, it has the form g(x) = g0 + g1x + … + gr-1 xr-1 + xr. We can also claim that g0 ≠ 0 , for if this were not the case, we could obtain a lower-degree code polynomial by cyclically shifting the codeword associated with g(x) one place to the left.

15

Page 18: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Property 2 in Theorem 1 suggests a convenient method for mapping data blocks onto codewords in a cyclic code. Let g(x) be the rth – degree generator polynomial for an (n,k) q-ary cyclic code. An (n-r)=k symbol data block (m0, m1, … , mk-1) can be associated with a message polynomial m0 + m1x + … + mr-1 xr-1 + xr = m(x) and encoded through multiplication by the generator polynomial :

g(x)m(x)c(x) ⋅= (2)

A systematic encoding algorithm for the same (n,k) code C is given by :

d(x)m(x)xc(x) k-n −⋅= (3)

where d(x) is the reminder resulted after we divide the information polynomial xn-k m(x) by the generator polynomial g(x). The polynomial multiplication in (2) can be expressed using matrices as shown below:

Gm

ggg00

0ggg000ggg

mC

r10

r1r0

r10

⋅=

⎥⎥⎥⎥

⎢⎢⎢⎢

⋅= −

KK

KKKKKKK

KK

KK

(4) where G is named the generator matrix of the cyclic code C. Because the lines of the generator matrix of a code are a basis for the vector space, it results that the polynomials g(x), xg(x), x2g(x), …xk-1g(x) are a basis for the cyclic code C. Puncturing a cyclic code, one gets a shortened code, which is also named polynomial code because the generator polynomial for the original cyclic code generates the shortened code as well (a shortened cyclic code is in fact the same as a pseudo-cyclic code, [4]-theorem 8.9 and 8.10). Since shortening decreases the rate of a code, polynomial codes have error detection and correction capabilities that is at least as good as those of the code from which they were derived. So, in this paper we shall consider the following definition for a polynomial code C Definition 2 : Let g(x) = g0 + g1x + … + gr-1 xr-1 + xr be a certain polynomial of degree (r-1). The set of all the multiples of g(x) of degree (n-1) or less is a polynomial code C. B. Linear UEP Codes We consider a linear (n,k) code C of length n and dimension k over GF(q)with generator matrix G. Definition 3. The separation vector s(G) = (s1(G), s2(G), …., sk(G)) is defined by:

( ) ( ) ( )( ){ }ki1

,0im,kqGFm|GmwtminGis

≤≤

≠∈=

(5) where wt(v) is the weight of the vector v. This separation vector s(G) guarantees the correct interpretation, [5], of the i-th message symbol whenever Nearest Neighbor Decoding is applied and no more than (sI(G)-1)/2 errors have occurred in the transmitted codeword. A linear code that has a generator matrix G such that the components of the separation vector s(G) are not mutually equal is called a Linear Unequal Error Protection (LUEP) code.

III. COMPUTATIONAL ALGORITHM The proposed algorithm uses the binary representation for polynomials and for vectors. We calculate all the codewords and then we establish the separation vector according to the definition 3. The main steps are: • get the desired separation vector and the starting

generator polynomial. • compute the base vectors of the span C: g(x),

xg(x), ,…, xk-1g(x). • compute all the codewords of the code. • compute all the components of the separation

vector for the generated code, one by one. • compare the obtained separation vector with the

desired one : if they match, print g(x) and stop else choose the another g(x) and continue.

IV. RESULTS

In order to implement the proposed algorithm we have designed several C++ programs able to provide UEP codes for distances 9,8,7 … and maximum length 31. The results we have obtained are synthetically presented in Appendix. In this table we have selected only the optimal codes (those with maximum separation vector). For each particular case the program has provided one or several generator polynomials (sometimes even 4 or 5) but for the space sake we have omitted them. To illustrate such cases we will consider the following exempla given in appendix : The UEP codes with parameters n=27 r=9 k=18 (n is the length of the code, r the number of check symbols and k the number of information symbols) can have the generator polynomials presented in Table 1. The codes provided by our algorithm are systematic ones, as described in (3). In table 1 the leftmost component in the separation vector represents the least significant information symbol (corresponding to

16

Page 19: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

the smallest degree in (3)) while the rightmost component represents the most significant information symbol.

Table 1 Generator polynomials for n=27 r=9 k=18

Separation vector Generator polynomial 444554444444444444 x9+x5+x4+x3+1

x9+x6+x5+x4+1

555555555555222222 x9+x8+x5+x4+x2+x+1

x9+x8+x7+x5+x4+x+1

444445444445544433 x9+x8+x6+x+1

266666662222222222 x9+x6+x5+x4+x3+1

x9+x8+x6+x3+x+1 In table 1 the components of the separation vector have been given exactly as they are provided by the program. It is of course possible to permute these information symbols so as to obtain separation vectors having nonincreasing components ( as presented in the Appendix) , but, in this case, the codes are not polynomial (cyclic or pseudo-cyclic) any more.

V. CONCLUSIONS Using our software we have succeeded to complete a table with all the polynomial UEP codes having length less than 32 and distances up to 9. The method can be extended in the same manner for any distances. Though, for codes with greater length the runtime increases dramatically, so that for codes longer than 63 the method becomes practically inoperant.

REFERENCES [1] Kazuteru N., Fujiwara E. : “Unequal Error Protection Codes with Two-Level Burst and Bit Error Correcting Capabilities”, Proc. of IEEE Int. Symp. Defect and Fault Tolerance in VLSI Systems, San Francisco, USA, pp.299-307, Oct. 2001. [2] Wicker S.: “Error Control Systems for Digital Communication and Storage”, Prentice Hall, New Jersey, 1995. [3] Lee L.H. Charles : “Error Control Block Codes for Communications Engineers”, Artech House, London, 2000. [4] Peterson W.W., Weldon Jr. E. J. : “Error Correcting Codes”, second edition, The MIT Press, Cambridge, 1972. [5] Tolhuizen L.M.G.M. : “On the Optimal Use and the Construction of Linear Block Codes”, Master’s Thesis, Eindhoven Univ. of Technology, Depart. of Mathematics and Comp. Science, 1986.

Appendix Binary optimal polynomial UEP codes

of length less than 32

n r k Separation vector 6 4 2 52

3 4 3333 Not UEP 4 3 522 ; 444 Not UEP

7

5 2 54 ; 62 3 5 33332 4 4 5222 ; 4442 ; 3333 Not UEP 5 3 544 ; 622 ; 4444 Not UEP

8

6 2 72 ; 64 ; 55 Not UEP 3 6 333322 4 5 52222 ; 44422 ;33333 5 4 6222 ; 4444 Not UEP 6 3 722 ; 554 ; 644

9

7 2 74 ; 55 Not UEP 3 7 3333222 4 6 444222 ; 333333 Not UEP 5 5 62222 ; 44444 Not UEP 6 4 7222 ; 5444 ; 5533 7 3 744 ; 664 ; 555 Not UEP

10

8 2 76 3 8 33322222 4 7 4442222 ; 3333333 Not UEP 5 6 622222 ; 444444 Not UEP 6 5 72222 ; 54333 7 4 8222 ; 6644 ; 5555 Not UEP 8 3 744 ; 844 ; 666 Not UEP

11

9 2 86 ; 77 Not UEP 3 9 332222222 4 8 44222222 ; 33333333 Not

UEP 5 7 4444444 Not UEP 6 6 722222 7 5 82222 ; 55544 ; 64444 ; 66222 8 4 7444 ; 5555 Not UEP

12

9 3 774 ; 755 ; 844 ; 666 Not UEP 3 10 3222222222 4 9 422222222 ; 333333333 Not

UEP 5 8 44444444 Not UEP 6 7 7222222 7 6 822222 ; 554444 ; 555333 ;

662222 8 5 74444 ; 66664 ; 55555 Not

UEP 9 4 7744 ; 7666 ; 8444

13

10 3 884 ; 777 Not UEP 4 10 3333333333 Not UEP 5 9 444444444 Not UEP 7 7 8222222 ; 5544444 ; 6622222 8 6 666444 ; 555555 Not UEP 9 5 77444 ; 84444 ; 66666 Not

UEP

14

10 4 8844 ; 8666 ; 7777 Not UEP 4 11 33333333333 Not UEP 15 5 10 4444444444 Not UEP

17

Page 20: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

n r k Separation vector 7 8 82222222 ; 54433333 ;

66222222 8 7 6644444 ; 5555555 Not UEP 9 6 744444 ; 666666 Not UEP

10 5 88444 ; 77777 Not UEP 4 12 333333333332 5 11 44444444442 ;

33333333333 Not UEP 6 10 4444444444 Not UEP 7 9 662222222 8 8 64444444 ; 55555555 Not

UEP 9 7 6666666 Not UEP 10 6 777772 ; 777444 ; 766633 ;

766544 ; 882222 ; 844444 11 5 88882 ; 88666 ; 88844 ;

77777 Not UEP 12 4 9944 ; 9888

16

13 3 998 4 13 3333333333322 5 12 444444444422 ;

333333333333 Not UEP 6 11 44444444444 Not UEP 7 10 6222222222 8 9 644444444 ; 555555555 Not

UEP 9 8 66666666 Not UEP 10 7 7777722 ; 7644444 ; 8822222 11 6 888822 ; 884444 ; 866444 ;

777777 Not UEP 12 5 99444 ; 96666 ; 88888 Not

UEP

17

13 4 9988 4 14 33333333333222 5 13 4444444444222 ;

3333333333333 Not UEP 6 12 444444444444 Not UEP 8 10 5555533333 ; 5555555552 ;

5555444444 9 9 666666662 ; 666666444 ;

555555555 Not UEP 10 8 77777222 ; 88222222 ;

66666666 Not UEP 11 7 8888222 ; 8844444 ;

7777777 Not UEP 12 6 974444 ; 966666 ; 888888 Not

UEP 13 5 99444 ; 98888

18

14 4 9998 4 15 333333333332222 5 14 44444444442222 ;

33333333333333 Not UEP 6 13 4444444444444 Not UEP 8 11 55555555522 ; 55555333333 ;

5554444444 9 10 6666666622 ; 6666644444 ;

5555555555 Not UEP

19

10 9 777772222 ; 882222222 ; 666666666 Not UEP

n r k Separation vector 11 8 88882222 ; 84444444 ;

77777777 Not UEP 12 7 9444444 ; 8888888 Not UEP 13 6 994444 ; 988888

14 5 99988 4 16 3333333333222222 5 15 444444444422222 ;

333333333333333 Not UEP 6 14 44444444444444 Not UEP 8 12 555555555222 ;

555553333333 ; 544444433333

9 11 66666666222 ; 66664444444 ; 55555555555 Not UEP

10 10 7777722222 ; 8822222222 ; 6666666666 Not UEP

11 9 888822222 ; 844444444 ; 777777777 Not UEP

13 7 9944444

20

14 6 999333 ; 998888 4 17 33333333322222222 5 16 4444444442222222 ;

3333333333333333 Not UEP 6 15 444444444444444 Not UEP 8 13 5555555552222 ;

5555333333333 9 12 666666662222 ;

666644444444 ; 555555555555 Not UEP

10 11 77777222222 ; 88222222222 ; 66666666666 Not UEP

11 10 8888222222 ; 8444444444 ; 7777777777 Not UEP

12 9 888888888 Not UEP 13 8 99444444 14 7 9944444 ; 10 933333 ;

9855555 ; 9666666

21

15 6 999993 ; 999988 4 18 333333332222222222 5 17 44444444222222222 ;

33333333333333333 Not UEP

6 16 4444444444444444 Not UEP 8 14 55555555522222 ;

55433333333333 9 13 6666666622222 ;

6644444444444 ; 5555555555555 Not UEP

10 12 777772222222 ; 882222222222 ; 666666666666 Not UEP

11 11 88882222222 ; 84444444444 ; 77777777777 Not UEP

12 10 8888888888 Not UEP 13 9 994444444 14 8 99333333 ; 98833333 ;

97444444 ; 96666666

22

15 7 9998888 ; 9999333 23 4 19 3333333222222222222

18

Page 21: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

n r k Separation vector 5 18 444444422222222222 ;

333333333333333333 6 17 44444444444444444 Not

UEP 8 15 555555555222222 ;

543333333333333 9 14 55555555555544 ;

66666666222222 ; 64444444444444

10 13 7777722222222 ; 8222222222222 ; 6666666666644 ; 5555555555555 Not UEP

11 12 888822222222 ; 844444444444 ; 777777777777 Not UEP

14 9 993333333 ;944444444 15 8 99993333 ; 99955555 ;

99666666

16 7 9999988 4 20 33333322222222222222 5 19 4444442222222222222 ;

3333333333333333333 Not UEP

6 18 444444444444444444 Not UEP

8 16 5555555552222222 9 15 555555555554444 ;

555555555555222 ; 666666662222222

10 14 77777222222222 ; 66666666666222 ; 66666666664444 ; 55555555555555 Not UEP

11 13 7777777777772 ; 8888222222222 ; 6666666666666 Not UEP

12 12 888888888882 ; 888444444444

14 10 9933333333 ; 9444444444 ; 7777777777 Not UEP

15 9 999555555 ; 976666666 ; 888888888 Not UEP

24

16 8 99999944 ; 99999666 ; 99998888

4 21 333332222222222222222 5 20 44444222222222222222 ;

33333333333333333333 Not UEP

6 19 4444444444444444444 Not UEP

8 17 55555555522222222 9 16 5555555544444444 ;

5555555555552222 ; 6666666622222222

25

10 15 777772222222222 ; 666666666662222 ; 666666664444444 ; 555555555555555 Not UEP

n r k Separation vector 11 14 77777777777722 ;

88882222222222 ; 66666666666666 Not UEP

12 13 8888888888822 ; 8884444444444

14 11 99333333333 ; 94444444444 ; 77777777777 Not UEP

15 10 9988333333 ; 9985555555 ; 9666666666 ; 8888888888 Not UEP

16 9 999998444 ; 999996666 ; 999977777 ; 999888888

4 22 3333222222222222222222 5 21 444422222222222222222 ;

333333333333333333333 Not UEP

6 20 44444444444444444444 Not UEP

8 18 555555552222222222 9 17 55544444444444444 ;

55555444444444443 ; 55555555555522222 ; 66666666222222222

10 16 7777222222222222 ; 6666666666622222 ; 6666666444444444 ; 5555555555555555 Not UEP

11 15 777777777777222 ; 888822222222222 ; 666666666666666 Not UEP

12 14 88888888888222 ; 88844444444444

14 12 933333333333 ; 777777777777 Not UEP

15 11 99444444444 ; 98888888888

26

16 10 9999884444 ; 9999777777 ; 9888866666

4 23 33322222222222222222222 5 22 4442222222222222222222 ;

3333333333333333333333 Not UEP

6 21 444444444444444444444 Not UEP

8 19 5555555222222222222 9 18 554444444444444444 ;

555555555555222222 ; 555444444444444433 ; 666666622222222222

10 17 77722222222222222 ; 66666666666222222 ; 66666664444444444 ; 55555555555555555 Not UEP

11 16 7777777777772222 ; 8882222222222222 ; 6666666666666666 Not UEP

12 15 888888888882222 ; 888444444444444

27

14 13 7777777777777 Not UEP

19

Page 22: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

n r k Separation vector 15 12 994444444444 ;

888888888888 Not UEP

16 11 99997777777 ; 98888844444 4 24 332222222222222222222222 5 23 44222222222222222222222 ;

33333333333333333333333 Not UEP

6 22 4444444444444444444444 Not UEP

8 20 55555522222222222222 9 19 5444444444444444444 ;

5555555555552222222 ; 6666662222222222222

10 18 772222222222222222 ; 666666666662222222 ; 666666444444444444 ; 555555555555555555 Not UEP

11 17 77777777777722222 ; 88222222222222222 ; 66666666666666666 Not UEP

12 16 8888888888822222 ; 8844444444444444

15 13 9944444444444 ; 7777777777777 Not UEP

28

16 12 999444444444 ; 987666666666 ; 987777444444 ; 888888888888 Not UEP

4 25 3222222222222222222222222 5 24 422222222222222222222222;

333333333333333333333333 Not UEP

29

6 23 44444444444444444444444 Not UEP

n r k Separation vector 8 21 555552222222222222222 9 20 55555555555522222222 ;

66666222222222222222 10 19 7222222222222222222 ;

6666666666622222222 ; 6666644444444444444 ; 5555555555555555555 Not UEP

11 18 777777777777222222 ; 822222222222222222 ; 666666666666666666 Not UEP

12 17 88888888888222222 ; 84444444444444444

15 14 77777777777777 Not UEP

16 13 9994444444444 ; 8888888888888 Not UEP

5 25 3333333333333333333333333 Not UEP

6 24 444444444444444444444444 Not UEP

8 22 5555222222222222222222 9 21 555555555555222222222 ;

666622222222222222222 10 20 66666666666222222222 ;

66664444444444444444 ; 55555555555555555555 Not UEP

11 19 7777777777772222222 ; 6666666666666666666 Not UEP

12 18 888888888882222222 15 15 777777777777777 Not UEP

30

16 14 99944444444444 ; 88888888888888 Not UEP

All the codes marked “Not UEP” are standard cyclic or pseudo-cyclic ones.

20

Page 23: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

A Wei’s Type Multidimensional TCM Encoder Florin DĂRĂBAN1

Abstract-This article presents a method for the construction of multidimensional TCM codes that have small CER (Constellation Extension Rate) and PAR (Peak-to-Average power Rate) parameters and hence are of high bandwidth efficiency. Using this method it is presented a generalization of Wei’s construction for the 2N-Dimensional TCM encoder. The final part presents a comparison between the construction proposed and Sterian’s construction in terms of CER, PAR and asymptotic coding gain. Keywords: trellis coded modulation, multidimensional trellis coded modulation, multidimensional signal constellation, Constellation Extension Rate (CER), Peak-to-Average power Rate (PAR), multidimensional trellis coded modulation encoder.

I. INTRODUCTION

For band limited channels trellis coded modulation (TCM) gives significant coding gains over uncoded transmission without the sacrifice of bandwidth efficiency η [1]. The cost is the enlargement of signals constellations.

For 2-D TCM codes to send Q information bits in each 2-D signaling interval, a 2-D signal constellation with 2Q+1 2-D signal points is used. This 2-D signal constellation is partitioned into 2m+1 2-D subsets with intrasubset minimum squared Euclidian distance (MSED) larger that minimum squared Euclidian distance of 2-D signal constellation. Of the Q information bits that arrive in each 2-D signaling interval:

m bits enter a rate-m/m+1 convolutional encoder and the resulting m+1 coded bits select which 2-D subset is to be used,

Q-m uncoded remaining bits select which 2-D signal point from the selected 2-D subset is to be transmitted [3].

The cost is that the size of 2-D signal constellation is doubled over uncoded transmission which means a 3-dB loss in the coding gain. This is due to the fact that 1 redundant bit is added every 2-D signaling interval.

This 3-dB loss in coding gain can be reduce using multidimensional TCM codes because lower than 1 redundant bit is added every 2-D signaling interval [2].

For 4-D TCM codes the loss in coding gain is 1,5 dB and for 8-D TCM codes the loss in coding gain is 0,75 dB [2, 4]. ____________________________ 1 ROMTELECOM-Digital Telephony Exchange Alcatel Oradea Phone:++40-59-421251, Fax:++40-59-466638 Email:[email protected]

For 2N-Dimensional TCM codes to send Q information bits in each 2-D signaling interval, a 2N-D multidimensional signal constellation with 2QN+1 2N-D signal points is used. This 2N-D multidimensional signal constellation is partitioned into 2m+1 2N-D subsets with intrasubset minimum squared Euclidian distance (MSED) larger that minimum squared Euclidian distance of 2N-D multidimensional signal constellation. Of the NQ information bits that arrive in each 2N-D signaling interval (block of N 2-D signaling intervals):

m bits enter a rate-m/m+1 convolutional encoder and the resulting m+1 coded bits select which 2N-D subset is to be used,

NQ-m uncoded remaining bits select which 2N-D signal point from the selected 2N-D subset is to be transmitted [3].

The first 4-D TCM code, called GCS (Gallager-Calderbank-Sloane) code was reported independently in [2] and [5]. However the GCS code can transmit only an unintegral number of bits in each 2-D signaling interval.

Wei has constructed 4-D, 8-D and 16-D TCM codes that can transmit an integral number of bits in each 2-D signaling interval but Wei’s construction is limited to dimensionalities which are power of 2 [3].

Piertobon&Costello have searched for multidimensional TCM codes with multidimensional rectangular signal constellations with optimum distance properties [6]. They employed block codes for partitioning multidimensional rectangular signal constellations, technique which was first used for partitioning multidimensional M-PSK signal sets [7]. Unfortunately they did not consider CER (Constellation Extension Rate) and PAR (Peak-to-Average power Rate) parameters which are very important in high speed modems. CER is the ratio between average energy of the signal constellation after extension (corresponding to a coded transmission) and the average energy of the signal constellation before extension (corresponding to an uncoded transmission). PAR is the ratio between the peak and the average energy of the signal constellation after extension.

Wang&Costello have presented a method for construction multidimensional TCM codes with shell mapping but only 4-D TCM codes were considered [8].

Sterian has presented a method for the extension of Wei’s construction of 2N-D TCM codes for N being nonpower of 2. He presented as examples 6-D

21

Page 24: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

and 12-D TCM codes but unfortunately he did not consider CER and PAR parameters [10, 12].

Dinh&Hashimoto have presented a method for the construction multidimensional TCM codes based on coset codes [9]. They have constructed multidimensional rectangular signal constellations with optimal (minimum) CER and PAR parameters for constituent 2-D signal constellations.

The advantages of the multidimensional TCM codes over the 2-D TCM codes are the following:

reducing of the loss in coding gain due to the extending of multidimensional signal constellations by reducing the number of redundant bits,

reducing of the size and the CER and PAR parameters for constituent 2-D signal constellations of multidimensional signal constellation,

possibility of transmitting an integral or an nonintegral number of bits in each 2-D signaling interval,

better immunity at phase ambiguities (phase jitter),

better complexity/performance tradeoff. The applications of the multidimesional TCM

codes are: analog voiceband modems, digital wireless modems, digital digital subscriber line (DSL) modems, digital satellite modems.

II. EXTENDING WEI’S CONSTRUCTION

FOR THE 2N-D TCM CODES

The construction of 2N-Dimensional TCM codes consist in the following steps:

construction of the 2N-D signal constellation,

partitioning of the 2N-D signal constellation, assignment of the 2N-D subsets at 2N-D

TCM code state transitions, mapping between NQ+1 bits (m+1

convolutionally encoded bits and NQ-m uncoded remaining bits) and 2N-D signal constellation.

A. Construction of 2N-D signal constellation For small values of NQ+1 and a data

communications system where additive white Gaussian noise (AWGN) is the only impairment, a 2N-D signal constellation as small as possible may be constructed.

For large values of NQ+1 or a data communications system where except additive white Gaussian noise (AWGN) other impairments such as linear or nonlinear distortion and phase jitter are also present, the construction of 2N-D signal constellation must respect the following requests [3]:

the size for constituent 2-D signal constellations of multidimensional signal constellation is kept as small as possible,

the CER and PAR parameters for constituent 2-D signal constellations of multidimensional signal constellation,

the complicated mapping between NQ+1 bits (m+1 convolutionally encoded bits and NQ-m uncoded remaining bits) and 2N-D signal constellation may be converted to N simple constituent 2-D signal constellation mappings.

First of all we construct a 2-D signal constellation. This 2-D signal constellation is a finite subset of Z2 lattice (2-D lattice) or is a finite subset of a translated, rotated, and/or scaled version of Z2 lattice.

We suppose that we have a 2-D signal constellation with 2Q+β2Q=(1+β)2Q 2-D signal points where Q=transmission rate of the 2N-D TCM code and β=rational number so that β2Q is an integer.

2-D signal constellation is made of 2 groups: o Inner Group (IG) = contains 2Q 2-D signal

points the same like the 2-D signal constellation used in an uncoded transmission for transmitting Q bits in each 2-D signaling interval,

o Outer Group (OG) = contains β2Q 2-D signal points.

These 2 groups IG and OG must respect the following 3 requests:

each group may be partitioned in 2-D subsets so that at each partitioning level intrasubset MSED to be as larger as possible,

each group may contain 2-D signal points placed as close as possible to origin of coordinates axes in complex plane so that average energy (Eaverage) of each group to be as small as possible. From this reason is used circular-shaped 2-D signal constellations. These circular-shaped 2-D signal constellations provide significant improvements (by several dB) of asymptotic coding gain for nonlinear communications channels [6]. As a result, there is always a circle centered at origin of coordinates axes of complex plane which framed a circular-shaped 2-D signal constellation. We suppose that IG is limited by circle C0(O,R0) and OG is limited by circles C0(O,R0) and C2(O,R2) where R2>R0,

each group may be invariant under a 90°, 180°, 270° rotation (rotational symmetry). By rotating a 2-D signal point from one group with 90°, 180°, 270° another 2-D signal point from the same group must be obtain. This request allows a demodulator to only have to lock within a 90° range, resulting in faster lock times [6]. Another important factor is that signal acquisition can be made with no training period ( no training sequences) (i.e., blind equalization).

The construction of rectangular 2N-D signal constellation (finite subset of Z2N lattice) is made by concatenating N constituent 2-D signal points and by eliminating those resultant 2N-D signal points which contain more than one 2-D signal point from OG.

The construction of nonrectangular 2N-D signal constellation (finite subset of D2N, E2N, DE2N lattice) is made by concatenating N constituent 2-D signal

22

Page 25: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

points and by eliminating those resultant 2N-D signal points which contain more than one 2-D signal point from OG or those resultant 2N-D signal points which are not valid points of nonrectangular lattice.

We are constructing 2N-D signal points by concatenating N constituent 2-D signal points. Thus:

• the number of 2N-D signal points which contain N constituent 2-D signal points from IG is 2NQ,

• the number of 2N-D signal points which contain (N-1) constituent 2-D signal points from IG and 1 constituent 2-D signal point from OG is βN2NQ.

Since a total of 2NQ+1=2NQ+2NQ 2N-D signal points are required we suppose that:

βN2NQ≥2NQ⇔β≥N

1 (1)

We suppose that every 2-D signal point from 2-D signal constellation has a Voronoi region of unit area. Likewise, we suppose that 2-D signal constellation contains so many 2-D signal points that average energy Eaverage is approximated by integration over the area confined by the circle C2(O,R2).

Simple extension-We are constructing 2N-D signal points by concatenating N constituent 2-D signal points. Thus:

• the number of 2N-D signal points which contain N constituent 2-D signal points from IG is 2NQ,

• the number of 2N-D signal points which contain (N-1) constituent 2-D signal points from IG and 1 constituent 2-D signal point

from OG in one of first β

1 positions is:

β

1βN2NQ=2NQ.

It results a total of 2NQ+1=2NQ+2NQ 2N-D signal points.

Fig.1. The 2-D signal constellation resulted by

simple extension.

Lemma 1-A 2N-D signal constellation limited by a circle C(O,ρ) of radius ρ and centered at the origin includes πρ2 2-D signal points and has the average

energy Eaverage= 2

2ρ .

Lemma 2-A 2N-D signal constellation limited by 2 circles C1(O,ρ1) and C2(O,ρ2) of radius ρ1, ρ2, (ρ1<ρ2) and centered at the origin includes

)21ρ

22π(ρ − 2-D signal points and has the average

energy Eaverage= 2

22ρ

21ρ +

.

We obtain: -number of 2-D signal point from IG: 2

0πRQ2 =

-average energy of IG: 2

20R

IGE =

-number of 2-D signal point from OG:

)20R2

2π(RQβ2 −=

-average energy of OG: 2

22R2

0ROGE

+=

In 2N-D signal points construction a 2-D signal point from IG is used 2N-1 more often than a 2-D signal point din OG. If pIG=using probability of a 2-D signal point from IG and pOG=using probability of a 2-D signal point from OG we have:

⎪⎪⎩

⎪⎪⎨

=

−=

⇔⎪⎩

⎪⎨

=+

−=

2N1

OGp

2N12N

IGp

1OGpIGp

12NOGpIGp

(2)

The average energy of 2-D signal constellation is:

OGE2N1

IGE2N

12NOGEOGpIGEIGpaverageE

+−

=

=+=

(3)

The CER and PAR parameters of 2-D signal constellation are:

β)1(2N2N1

IGEOGE

2N1

2N12N

IGEaverageE

CER

++=

=+−

==

(4)

β)(1CER

2

2

20R

22R

CER1

IGEpeakE

CER1

averageEpeakE

PAR

+==

===

(5)

If N=power of 2 then:

⎪⎪⎪

⎪⎪⎪

+=

++=

=

)N1(1

0CER2

0PAR

)N11(2N

2N1

0CER

N1β

(6)

23

Page 26: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

If N=nonpower of 2 then:

⎪⎪⎪

⎪⎪⎪

′+=

′++=

′=

)N1(1

1CER2

1PAR

)N11(2N

2N1

1CER

N1β

(7)

where N′ =the largest power of 2 lower than N. Optimal extension-External group OG is divided

in 2 subgroups with a circle C1(O,R1) of radius R1 where R0<R1<R2 and centered at origin:

o low average energy external subgroup (OGL) = contains β(1-α)2Q 2-D signal points where α=rational number so that 0≤α<1,

o high average energy external subgroup (OGH) = contains βα2Q 2-D signal points.

We are constructing 2N-D signal points by concatenating N constituent 2-D signal points. Thus:

• the number of 2N-D signal points which contain N constituent 2-D signal points from IG is 2NQ,

• the number of 2N-D signal points which contain (N-1) constituent 2-D signal points from IG and 1 constituent 2-D signal point from OGL in one of first N positions is: Nβ(1-α)2NQ

Fig.2 The 2-D signal constellation resulted by

optimal extension.

Since 2NQ+1=2NQ+2NQ 2N-D signal points are totally required it results that we need to construct further 2NQ+1-2NQ-Nβ(1-α)2NQ=βα(N-P)2NQ 2N-D

signal points, where βα

1βNP −= , 0≤P≤N.

If P is an integer we will consider 2N-D signal points which contains N-1 constituent 2-D signal points from IG and 1 constituent 2-D signal point from OGH in one of the first N-P positions, namely βα(N-P)2NQ 2N-D signal points.

It results a total of 2NQ+1=2NQ+Nβ(1-α)2NQ+βα(N-P)2NQ 2N-D signal points.

Because 0≤P≤N⇔0≤N-P≤N and βα

1βNP −=

result that α)N(1

1βN1

−≤≤ .

The average energy of 2-D signal constellation is:

HOGEHOGp

LOGELOGpIGEIGpaverageE

+

++=

(8) where pIG=using probability of a 2-D signal point from IG and LOGp ,

HOGp =using probabilities of

a 2-D from OGL, OGH:

⎪⎪⎪

⎪⎪⎪

−=

=

−=

⎪⎪⎪⎪⎪

⎪⎪⎪⎪⎪

−−

=

=++

−=+

αP)2N(NP)-α(N

HOGp

αP)-2(Nα)-(1

LOGp

2N12N

IGp

P)βα(Nα)Nβ(1

HOGpLOGp

1HOGpLOGpIGp

12NHOGp

LOGpIGp

(9)

We obtain:

HOGEαP)2N(NP)-α(N

LOGEαP)-2(Nα)-(1

IGE2N

12NaverageE

−+

++−

=(10

) The CER and PAR parameters of 2-D signal

constellation are (after some calculations):

]N1-β][β-

α)N(11[

2α)(1

0CER

IGEHOGE

αP)2N(NP)-α(N

IGELOGE

αP)-2(Nα)-(1

2N12NCER

−−

+=

=−

+

++−

=

(11)

]N1-β][β-

α)N(11[

2α)(1

0CER

β)2(1

β)(1CER

2PAR

−−

+

+=

=+=

(12)

Because 0≤α<1 and α)N(1

1βN1

−≤≤ , if α is

closer to 0 then β is closer to N1 and the CER and

PAR parameters are smaller. If Q=transmission rate of 2N-D TCM code and α,

β are 2 rational numbers so that β2Q =integer and

0≤α<1, α)N(1

1βN1

−≤≤ then the CER parameter of

constituent 2-D signal constellation is:

24

Page 27: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

2α)N8(1

2α0CERCER0CER

−+≤≤ (13)

We note:

⎪⎪

⎪⎪

==

=

=

Q1)2-N (βJPK

Qβα2J

Qβ2I

(14)

Result:

⎪⎪⎩

⎪⎪⎨

=

+==

JKP

NKQ2I(K)I

(15)

Let K0 be the smallest positive integer so that I(K0) is also an integer. Such an integer K0 always exists and if it is given K0 then for an arbitrary positive integer R it results that K=K0+RN is an integer and I(K) is an integer, too.

Let J0 be the smallest positive integer so that

0J0K

P = is also an integer. Such an integer J0 always

exists and it is greater or equal to 1. Lemma 3-For a dimension N and a transmission

rate Q we are constructing a 2-D signal constellation with the minimal CER and PAR parameters if [9]:

⎪⎪⎪⎪

⎪⎪⎪⎪

=

=

=

0KP

)0I(K1α

Q2

)0I(Kβ

(16)

It results a 2-D signal constellation which contains:

2Q 2-D signal points in group IG,

I(K0)-1 2-D signal points in subgroup OGL,

1 2-D signal point in subgroup OGH.

Every group (subgroup) is rotationally invariant at a rotation of 90°, 180°, 270° if I and J are multiple of 4.

Let ′0K be the smallest positive integer so that

4

)0I(4K ′ is also an integer.

Lemma 4-For a dimension N and a transmission rate Q we are constructing a rotationally invariant 2-D signal constellation with the minimal CER and PAR parameters if [9]:

⎪⎪⎪⎪

⎪⎪⎪⎪

′=

′=

′=

0KP

)0I(4K

Q2

)0I(4Kβ

(17)

It results an invariant rotationally 2-D signal constellation which contains:

2Q 2-D signal points in group IG,

I(4K0′)-4 2-D signal points in subgroup OGL,

4 2-D signal point in subgroup OGH.

For Wei’s construction (N=power of 2) [3] we have:

⎪⎪⎪

⎪⎪⎪

=

==

=

0PARWEIPAR0CERWEICER

0αN1β

(18)

For Sterian’s construction (N=nonpower of 2) [10, 11, 12] we have:

⎪⎪⎪⎪⎪⎪

⎪⎪⎪⎪⎪⎪

−′′

−+

′+

=

−′′

−+=

=

′=

)N1

N1)(

N1

N2(

41

0CER

)N12(1

STERIANPAR

)N1

N1)(

N1

N2(

41

0CERSTERIANCER

21α

N1β

(19) where N′ =the largest power of 2 lower than N. If N=power of 2 then:

⎪⎩

⎪⎨⎧

=

=

0αN1β

(20)

If N=nonpower of 2 then:

⎪⎪⎪

⎪⎪⎪

′=

′=

)0I(4K

Q2

)0I(4Kβ

(21)

where ′0K is the smallest integer so that

4N04KQ2

4

)0I(4K ′+=

′ is an integer.

25

Page 28: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

B. Partitioning the 2N-D signal constellation in 2N-D subsets

Suppose that we have a 2N-D signal constellation

with 20dMSED = and we would like to partition this

in 2N-D subsets with 20d2dMSED >= .

The partitioning of the 2N-D signal constellation in 2N-D subsets is made in a different way for N=even / odd, thus:

1. we partition each of these 2 / N constituent N-D

/ 2-D signal constellations with 20dMSED = in N-D /

2-D families, N-D / 2-D subfamilies and N-D / 2-D subsets with increasing MSED.

Each partitioning level of N-D / 2-D signal constellation increases MSED by a factor of 2 (binary partitioning) until we obtain N-D / 2-D subsets with

20d2dMSED >= .

After the first partitioning level of N-D / 2-D signal constellation we obtain N-D / 2-D families and after the next partitioning levels except the last one we obtain N-D / 2-D subfamilies. After the last partitioning level we obtain N-D / 2-D subsets.

The finer is the partitioning of N-D / 2-D signal constellation the more N-D / 2-D subsets with larger MSED we obtain.

2. we construct 2N-D types with 20d2dMSED >= by concatenating 2 / N constituent

N-D / 2-D subsets. 3. we construct 2N-D subsets with

20d2dMSED >= by grouping S=2s constituent 2N-

D types. The grouping of the 2N-D types in the 2N-D subsets must be made so that:

the construction of 2N-D TCM code may be as simple as possible (may obtain a number of 2N-D subsets as small as possible so that the selection of a 2N-D subset may be made with as small as possible number of bits convolutionally encoded),

each 2N-D subset may be rotationally invariant under as many rotations as possible (phase ambiguities of 2N-D signal constellation). If it is not possible for each 2N-D subset to be rotationally invariant under all rotations then each rotation would at least transform a 2N-D subset in another 2N-D subset.

If N=even then S=the number of N-D subsets comprised in a N-D subfamily.

If N=odd then S=2Nl-m-1 where U=2u is the number of 2-D subsets of constituent 2-D signal constellation.

4. we group 2N-D subsets in 2N-D subfamilies and 2N-D families with decreasing MSED.

Each grouping level of 2N-D subsets reduces MSED with a factor of 2 until we obtain 2N-D

families with 20d2MSED = .

C. Assignment of the 2N-D subsets at 2N-D TCM code state transitions

The assignment of the 2N-D subsets at 2N-D TCM code state transitions is made with respect of 3 requests [3]:

1. the 2N-D subsets associated with transitions leading from a state are different from each other and belong to the same 2N-D family and likewise for 2N-D subsets associated with transitions leading to a state

2. the MSED between 2 sequences of 2N-D subsets corresponding to 2 distinct trellis paths is

larger than or equal to 2d2freed = which is the

MSED of each 2N-D subset (the intersubset 2N-D MSED is larger than or equal to the intrasubset 2N-D MSED)

3. if X is the 2N-D subset associated with transition leading from the current state nσ to the

next state Nnσ + and if X1, X2 ,X3 are 2N-D subsets

obtained when X is rotated with 90°, 180°, 270° then 3 mapping functions F1, F2, F3 may be defined between 2N-D TCM code states so that X1, X2, X3 to be associated with transitions from the current states

)n(σ1F , )n(σ2F , )n(σ3F to the next states

)Nn(σ1F + , )Nn(σ2F + , )Nn(σ3F + . The second requirement guarantees that the MSED

between any 2 sequences of 2N-D signal points is 2d2

freed = and eliminates error events which differ in more than one 2N-D signal point from the correct sequence of 2N-D signal points. The error coefficient Nfree of the 2N-D TCM code is equal to the number of nearest neighbours to any 2N-D signal point in the same 2N-D subset with a finite number of 2N-D signal points. If we do not neglect boundary effect then the error coefficient of 2N-D TCM code is lower than in the previous definition.

The third requirement guarantees that we will obtain a 2N-D TCM code transparent to all phase ambiguities of the 2N-D signal constellation.

D. Mapping between NQ+1 coded bits and 2N-D signal constellation

The mapping between NQ+1 coded bits and 2N-D signal constellation is converted in N simple mappings of constituent 2-D signal constellations with a bit converter and a block encoder.

The bit converter and the block encoder transform NQ+1 coded bits (m+1 convolutionally encoded bits and NQ-m uncoded remaining bits) in N groups of Q+1 bits each which means NQ+N bits.

Each group of Q+1 bits addresses a 2-D mapping block and selects a 2-D signal point. In this way we select N constituent 2-D signal points and by their concatenation we obtain a 2N-D signal point corresponding to these NQ+1 bits.

III. BLOCK DIAGRAM OF THE 2N-D TCM ENCODER

The block diagram of 2N-D TCM is presented in

Fig.3.

26

Page 29: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

A 2N-D signal constellation with 2NQ+1 2N-D signal points is used. The construction of 2N-D signal constellation and the partitioning of this constellation in 2N-D subsets is made like in the previous paragraphs II.A and II.B.

The first m input bits are coded with a convolutional encoder with rate m/m+1 and V=2v states. We note current state and next state of the convolutional encoder: W1,p, W2,p ,…, Wv,p, where p=n (current state) and p=n+N (next state).

Decimal value of state pσ equals:

pv,Wp1,vW12...p1,W1v2pσ +−++−= (22)

where p=n (current state) and p=n+N (next state). We assume that the number of 2N-D subsets from

a 2N-D family is equal with F, where it is neccesary that F≤V.

The set of current states { }nσ is partitioned in F subsets:

{ }1Fj0 1,Fi0 jFi −≤≤−≤≤+ (23)

The set of next states { }Nnσ + is partitioned in F subsets:

{ }1Fk0 1,Fj0 kFj −≤≤−≤≤+ (24)

The connectivity of the trellis diagram of the 2N-D TCM code is made so that for any given 0≤j≤F-1 there are state transitions between every current state Fi+j, 0≤i≤F-1 and every next state Fj+k, 0≤k≤F-1.

We determined the rotations of the 2N-D subsets at the succesive rotations by 90° of the 2-D subsets and the rotations of the convolutional encoder states at the succesive rotations by 90° of the 2N-D subsets. From the rotations of the convolutional encoder states we deduced the mapping functions F1, F2 and F3.

The assignment of 2N-D subsets at state transitions of 2N-D TCM code is made like in the section II.C.

At state transitions leading from even states (Y0,n=Wv,n=0) are assigned 2N-D subsets from 2N-D family noted F0.

At state transitions leading from odd states (Y0,n=Wv,n=1) are assigned 2N-D subsets from 2N-D family noted F1.

A systematic feedback convolutional encoder is used which means that input bits I1,n, I2,n,…,Im,n are directly connected to output. Thus only Y0,n bit is convolutionally encoded and depends of input bits I1,n, I2,n,…,Im,n and current state bits W1,n, W2,n ,…, Wv,n.

From the trellis diagram of the 2N-D TCM code we determined the relations for next state bits W1,n+N, W2,n+N ,…, Wv,n+N.

The m+1 bits from the output of convolutional encoder select with the help of a bit converter the 2N-D subset which will be used and the NQ-m bits remaining uncoded select with the help of a block encoder the 2N-D signal point which will be transmitted from previous selected 2N-D subset.

Let U=2u be the number of 2-D subsets of the constituent 2-D signal constellation.

If N=even at the bit converter input: ⇒ the first m+1 bits select the 2N-D subset, ⇒ the next s bits select the 2N-D type in the

previous selected 2N-D subset, ⇒ the next Nu-m-1-s bits select the N-D type

for each of the 2 constituent N-D subsets of the 2N-D type and so on until the selection of the N constituent 2-D subsets.

If N=odd at the bit converter input: ⇒ the first m+1 bits select the 2N-D subset, ⇒ the next s bits select the 2N-D type in the

previous selected 2N-D subset and the N constituent 2-D subsets implicitly.

The bit converter converts the Nu input bits Y0,n, I1,n, I2,n,…,Ir-1,n+c in N groups of u bits: Z0,p, Z1,p ,…, Zu-1,p, p=n, n+1, …, n+N-1 which select N constituent 2-D subsets corresponding to the selected 2N-D type in the used 2N-D subset, where r and c are the rest and

the remainder of the operation Q

Nu.

Let X be the 2N-D type associates with bit pattern cn1,-rcn2,-rbna,bn1,an2,n1,n0, I ,I ,...,I I,...,I ,I,Y ++++− ′′

and let be X1, X2, X3 the 2N-D types obtained by rotation of X with 90°, 180°, 270°, where we have

1ra2 −≤≤ and cb0 ≤≤ . Let 1bna,bn1,a )I I( ++− ′′ , 2bna,bn1,a )I I( ++− ′′ ,

3bna,bn1,a )I I( ++− ′′ be bit pairs obtained by the translation of bit pair )I I( bna,bn1,a ++− ′′ with 1, 2 or 3 positions in circular sequence 00→10→01→11→00. Then the 2N-D types associated with bits patterns:

cn1,-rcn2,-r1bna,bn1,an2,n1,n0, I ,I ,...,)I I(,...,I ,I,Y ++++− ′′

cn1,-rcn2,-r2bna,bn1,an2,n1,n0, I ,I ,...,)I I(,...,I ,I,Y ++++− ′′

cn1,-rcn2,-r3bna,bn1,an2,n1,n0, I ,I ,...,)I I(,...,I ,I,Y ++++− ′′ are X1, X2 ,X3.

For constructing a 2N-D TCM code transparent at any phase ambiguities of 2N-D signal constellation a 2 bits differential encoder of the form is used:

)mod4I II I()I I(

bna,bn1,a

N-bna,N-bn1,abna,bn1,a

++−

++−++− +′′=′′ (25)

The relations between the outputs and the inputs of the differential encoder are:

⎪⎩

⎪⎨⎧

′⊕=′

′⊗⊕′⊕=′

+−+−+−

+−+−+++

)I(I I

)I(I)I(I I

N-bn,1abn,1abn,1a

N-bn,1abn,1aN-bna,bna,bna,

(26) The NQ-Nu+1 remaining input bits are coded with

a block encoder which outputs N groups of Q-u+1 bits which select the N constituent 2-D signal points so that at most one is placed in OG

The asymptotic coding gain of the 2N-D TCM code over an uncoded transmission is:

[dB] CER

120d

2d1010logγ

⎟⎟⎟

⎜⎜⎜

⎛= (27)

where: 2d2

freed = =MSED of the 2N-D subsets obtained by partitioning of the 2N-D signal constellation,

27

Page 30: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

20d =MSED of the 2-D signal constellation used in an

uncoded transmission, CER=Constellation Extension Rate of the 2-D signal constellation constituent of the 2N-D signal constellation.

IV. CONCLUSIONS

The presented construction allows the generalisation of Wei’s construction of the 2N-D TCM codes for a dimension N equal to a power of 2 or a nonpower of 2 and allows the obtaining of better CER, PAR and γ parameters relative to Sterian’s construction which become a particular case of this

construction (21α = ).

For a given N the greater Q is the lower are the CER and PAR parameters and the greater is the γ parameter relative to Sterian’s construction (Table 1).

For a given Q the greater N is the lower is the improvement of CER, PAR and γ parameters relative to Sterian’s construction but the total number of 2-D signal points of constituent 2-D signal constellations of 2N-D signal constellation is smaller.

For a given N and Q the greater 2

0dd

⎟⎟

⎜⎜

⎛ is the

greater is the coding gain γ relative to an uncoded transmission.

The paid cost consists in more complexity for block encoder especially for great values of N. This is not a critical cost because in practice we are constructing 2N-D TCM codes for N≤8 and in present the cost of memories is smaller.

In choosing the N, Q, 2

0dd

⎟⎟⎠

⎞⎜⎜⎝

⎛, m and v it is

necessary to make a very careful trade-off between the complexity of 2N-D TCM code and the values obtained for the CER, PAR and γ parameters.

ACKNOWLEDGEMENT

The author would like to thank the professor

Miranda NAFORNIŢĂ and the professor Ioan NAFORNIŢĂ from Faculty of Electronics and Telecommunications Timişoara for their encouragement and guidance in preparing his paper.

REFERENCES [1] G. UNGERBOECK -„Channel coding with multilevels/phase signals”-IEEE Trans. Inf. Theory, Vol. IT-28, No. 1, pag. 56-67, Jan. 1982 [2] G. D. FORNEY Jr., R. G. GALLAGER, G. R. LANG, F. M. LONGSTAFF, S. U. QURESHI -„Efficient modulation for bandlimited channels”-IEEE J. Select. Areas. Comms, Vol. SAC-2, No. 5, pag. 632-647, Sept. 1984 [3] L. -F. Wei „Trellis-Coded Modulation with multidimensional constellations”-IEEE J. Trans. Inf. Theory, Vol. IT-33, No. 4, pag. 483-501, July. 1987 [4] G. D. FORNEY Jr. -„Geometrically uniform codes”, IEEE Trans. Inf. Theory, Vol. IT-37, No. 9, pag. 1241-1260, Sept. 1991 [5] A. R. Calderbank, N. J. A. Sloane -„Four-dimensional modulation with eight-state trellis code”, AT&T Tech. Journal, Vol. 64, pag. 1005-1018, May/June 1985 [6] S. S. PIETROBON , D. J. COSTELLO -„Trellis coding modulation with multidimensional QAM signals sets”, IEEE Trans. Inf. Theory, Vol. IT-39, No. 3, pag. 325-336, Mar. 1993 [7] S. S. PIETROBON, R. H. DENG, A. LAFANACHERE, G. UNGERBOECK, D. J. COSTELLO -„Trellis-coded multidimensional phase modulation”, IEEE Trans. Inf. Theory, Vol. IT-36, No. 3, pag. 63-89, Jan. 1990 [8] F. Q. WANG, D. J. COSTELLO -„New rotationally invariant four-dimensional trellis codes”, IEEE Trans. Inf. Theory , Vol. IT-42, pag. 291-300, Jan. 1996 [9] T. C. DINH, T. HASHIMOTO -„A systematic approach to construction of bandwith-efficient multidimensional trellis codes”, IEEE Trans. Comms., Vol. 48, No. 11, Nov. 2000 [10] C. -E. D. STERIAN -„Extending Wei’s trellis coded modulation technique with 2N-D rectangular constellation for N not a power of 2”, Telecomunicaţii, Anul XXI, Nr. 4, 1994 [11] C. -E. D. STERIAN -„128-state, rate-4/5 rotationally invariant trellis code with 4-D rectangular signal constellation having a coding gain of 5,63 dB”, Telecomunicaţii, Anul XXIII, Nr. 2, 1996 [12] C. -E. D. STERIAN -„Wei-type trellis-coded modulation with 2N-dimensional rectangular constellation for N not a power of 2”, IEEE Trans. Inf. Theory, Vol. IT-43, No. 3, pag. 750-758, Mar. 1997.

28

Page 31: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Fig.3 The block diagram of the 2N-D TCM encoder.

29

Page 32: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Table 1 The CER, PAR and γ parameters for Wei's, Sterian's and proposed construction

Q N N' (d/d0)2 α β CER0 CER PAR CER0 CER PAR γ Total CER PAR CER PAR γ Total CER PAR CER PAR γ Total

signal WEI WEI WEI WEI WEI signal STERIAN STERIAN STERIAN STERIAN STERIAN signal

[bits/s] [dB] [dB] [dB] [dB] points [dB] [dB] [dB] points [dB] [dB] [dB] points 7 2 2 4 0,00000 0,50000 1,37500 1,37500 2,18182 1,38303 1,38303 3,38819 4,63757 192 1,37500 2,18182 1,38303 3,38819 4,63757 192 - - - - - - 7 3 2 4 0,09091 0,34375 1,22222 1,22233 2,19867 0,87150 0,87189 3,42160 5,14871 172 - - - - - - 1,22917 2,44068 0,89611 3,87510 5,12449 192 7 4 4 4 0,00000 0,25000 1,15625 1,15625 2,16216 0,63052 0,63052 3,34888 5,39008 160 1,15625 2,16216 0,63052 3,34888 5,39008 160 - - - - - - 7 5 4 4 0,14286 0,21875 1,12000 1,12012 2,17611 0,49218 0,49263 3,37681 5,52797 156 - - - - - - 1,12188 2,22841 0,49944 3,47996 5,52116 160 7 6 4 4 0,16667 0,18750 1,09722 1,09733 2,16434 0,40295 0,40338 3,35326 5,61722 152 - - - - - - 1,09896 2,27488 0,40981 3,56959 5,61079 160 7 7 4 4 0,20000 0,15625 1,08163 1,08175 2,13774 0,34080 0,34128 3,29954 5,67932 148 - - - - - - 1,08259 2,30928 0,34464 3,63476 5,67596 160 7 8 8 4 0,00000 0,12500 1,07031 1,07031 2,10219 0,29511 0,29511 3,22672 5,72549 144 1,07031 2,10219 0,29511 3,22672 5,72549 144 - - - - - -

Q N N' (d/d0)2 α β CER0 CER PAR CER0 CER PAR γ Total CER PAR CER PAR γ Total CER PAR CER PAR γ Total signal WEI WEI WEI WEI WEI signal STERIAN STERIAN STERIAN STERIAN STERIAN signal

[bits/s] [dB] [dB] [dB] [dB] points [dB] [dB] [dB] points [dB] [dB] [dB] points 10 2 2 4 0,00000 0,50000 1,37500 1,37500 2,18182 1,38303 1,38303 3,38819 4,63757 1536 1,37500 2,18182 1,38303 3,38819 4,63757 1536 - - - - - - 10 3 2 4 0,01163 0,33594 1,22222 1,22222 2,18608 0,87150 0,87151 3,39665 5,14909 1368 - - - - - - 1,22917 2,44068 0,89611 3,87510 5,12449 1536 10 4 4 4 0,00000 0,25000 1,15625 1,15625 2,16216 0,63052 0,63052 3,34888 5,39008 1280 1,15625 2,16216 0,63052 3,34888 5,39008 1280 - - - - - - 10 5 4 4 0,01923 0,20313 1,12000 1,12000 2,14844 0,49218 0,49218 3,32122 5,52841 1232 - - - - - - 1,12188 2,22841 0,49944 3,47996 5,52116 1280 10 6 4 4 0,02326 0,16797 1,09722 1,09722 2,12895 0,40295 0,40295 3,28166 5,61765 1196 - - - - - - 1,09896 2,27488 0,40981 3,56959 5,61079 1280 10 7 4 4 0,02703 0,14453 1,08163 1,08163 2,11630 0,34080 0,34081 3,25577 5,67979 1172 - - - - - - 1,08259 2,30928 0,34464 3,63476 5,67596 1280 10 8 8 4 0,00000 0,12500 1,07031 1,07031 2,10219 0,29511 0,29511 3,22672 5,72549 1152 1,07031 2,10219 0,29511 3,22672 5,72549 1152 - - - - - -

Q N N' (d/d0)2 α β CER0 CER PAR CER0 CER PAR γ Total CER PAR CER PAR γ Total CER PAR CER PAR γ Total signal WEI WEI WEI WEI WEI signal STERIAN STERIAN STERIAN STERIAN STERIAN signal

[bits/s] [dB] [dB] [dB] [dB] points [dB] [dB] [dB] points [dB] [dB] [dB] points 7 2 2 8 0,00000 0,50000 1,37500 1,37500 2,18182 1,38303 1,38303 3,38819 7,64787 192 1,37500 2,18182 1,38303 3,38819 7,64787 192 - - - - - - 7 3 2 8 0,09091 0,34375 1,22222 1,22233 2,19867 0,87150 0,87189 3,42160 8,15901 172 - - - - - - 1,22917 2,44068 0,89611 3,87510 8,13479 192 7 4 4 8 0,00000 0,25000 1,15625 1,15625 2,16216 0,63052 0,63052 3,34888 8,40038 160 1,15625 2,16216 0,63052 3,34888 8,40038 160 - - - - - - 7 5 4 8 0,14286 0,21875 1,12000 1,12012 2,17611 0,49218 0,49263 3,37681 8,53827 156 - - - - - - 1,12188 2,22841 0,49944 3,47996 8,53146 160 7 6 4 8 0,16667 0,18750 1,09722 1,09733 2,16434 0,40295 0,40338 3,35326 8,62752 152 - - - - - - 1,09896 2,27488 0,40981 3,56959 8,62109 160 7 7 4 8 0,20000 0,15625 1,08163 1,08175 2,13774 0,34080 0,34128 3,29954 8,68962 148 - - - - - - 1,08259 2,30928 0,34464 3,63476 8,68626 160 7 8 8 8 0,00000 0,12500 1,07031 1,07031 2,10219 0,29511 0,29511 3,22672 8,73579 144 1,07031 2,10219 0,29511 3,22672 8,73579 144 - - - - - -

Q N N' (d/d0)2 α β CER0 CER PAR CER0 CER PAR γ Total CER PAR CER PAR γ Total CER PAR CER PAR γ Total signal WEI WEI WEI WEI WEI signal STERIAN STERIAN STERIAN STERIAN STERIAN signal

[bits/s] [dB] [dB] [dB] [dB] points [dB] [dB] [dB] points [dB] [dB] [dB] points 10 2 2 8 0,00000 0,50000 1,37500 1,37500 2,18182 1,38303 1,38303 3,38819 7,64787 1536 1,37500 2,18182 1,38303 3,38819 7,64787 1536 - - - - - - 10 3 2 8 0,01163 0,33594 1,22222 1,22222 2,18608 0,87150 0,87151 3,39665 8,15939 1368 - - - - - - 1,22917 2,44068 0,89611 3,87510 8,13479 1536 10 4 4 8 0,00000 0,25000 1,15625 1,15625 2,16216 0,63052 0,63052 3,34888 8,40038 1280 1,15625 2,16216 0,63052 3,34888 8,40038 1280 - - - - - - 10 5 4 8 0,01923 0,20313 1,12000 1,12000 2,14844 0,49218 0,49218 3,32122 8,53871 1232 - - - - - - 1,12188 2,22841 0,49944 3,47996 8,53146 1280 10 6 4 8 0,02326 0,16797 1,09722 1,09722 2,12895 0,40295 0,40295 3,28166 8,62795 1196 - - - - - - 1,09896 2,27488 0,40981 3,56959 8,62109 1280 10 7 4 8 0,02703 0,14453 1,08163 1,08163 2,11630 0,34080 0,34081 3,25577 8,69009 1172 - - - - - - 1,08259 2,30928 0,34464 3,63476 8,68626 1280 10 8 8 8 0,00000 0,12500 1,07031 1,07031 2,10219 0,29511 0,29511 3,22672 8,73579 1152 1,07031 2,10219 0,29511 3,22672 8,73579 1152 - - - - - -

30

Page 33: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

A Wei’s Type Multidimensional TCM Decoder Florin DĂRĂBAN1

Abstract-Using the method for the construction of multidimensional TCM codes that have small CER (Constellation Extension Rate) and PAR (Peak-to-Average power Rate) parameters this article presents a generalization of Wei’s construction for the 2N-Dimensional TCM decoder. Keywords: trellis coded modulation, multidimensional trellis coded modulation, multidimensional signal constellation, Constellation Extension Rate (CER), Peak-to-Average power Rate (PAR), multidimensional trellis coded modulation decoder.

I. INTRODUCTION

For band limited channels trellis coded

modulation (TCM) gives significant coding gains over uncoded transmission without the sacrifice of bandwidth efficiency η [1]. The cost is the enlargement of signals constellations.

For 2-D TCM codes to send Q information bits in each 2-D signaling interval, a 2-D signal constellation with 2Q+1 2-D signal points is used. This 2-D signal constellation is partitioned into 2m+1 2-D subsets with intrasubset minimum squared Euclidian distance (MSED) larger that minimum squared Euclidian distance of 2-D signal constellation. Of the Q information bits that arrive in each 2-D signaling interval:

m bits enter a rate-m/m+1 convolutional encoder and the resulting m+1 coded bits select which 2-D subset is to be used,

Q-m uncoded remaining bits select which 2-D signal point from the selected 2-D subset is to be transmitted [3].

The cost is that the size of 2-D signal constellation is doubled over uncoded transmission which means a 3-dB loss in the coding gain. This is due to the fact that 1 redundant bit is added every 2-D signaling interval.

This 3-dB loss in coding gain can be reduce using multidimensional TCM codes because lower than 1 redundant bit is added every 2-D signaling interval [2].

For 4-D TCM codes the loss in coding gain is 1,5 dB and for 8-D TCM codes the loss in coding gain is 0,75 dB [2, 4]. ____________________________ 1 ROMTELECOM-Digital Telephony Exchange Alcatel Oradea Phone:++40-59-421251, Fax:++40-59-466638 Email:[email protected]

For 2N-Dimensional TCM codes to send Q information bits in each 2-D signaling interval, a 2N-D multidimensional signal constellation with 2QN+1 2N-D signal points is used. This 2N-D multidimensional signal constellation is partitioned into 2m+1 2N-D subsets with intrasubset minimum squared Euclidian distance (MSED) larger that minimum squared Euclidian distance of 2N-D multidimensional signal constellation. Of the NQ information bits that arrive in each 2N-D signaling interval (block of N 2-D signaling intervals):

m bits enter a rate-m/m+1 convolutional encoder and the resulting m+1 coded bits select which 2N-D subset is to be used,

NQ-m uncoded remaining bits select which 2N-D signal point from the selected 2N-D subset is to be transmitted [3].

The first 4-D TCM code, called GCS (Gallager-Calderbank-Sloane) code was reported independently in [2] and [5]. However the GCS code can transmits only an unintegral number of bits in each 2-D signaling interval.

Wei has constructed 4-D, 8-D and 16-D TCM codes that can transmit an integral number of bits in each 2-D signaling interval but Wei’s construction is limited to dimensionalities which are power of 2 [3].

Piertobon&Costello have searched for multidimensional TCM codes with multidimensional rectangular signal constellations with optimum distance properties [6]. They employed block codes for partitioning multidimensional rectangular signal constellations, technique which was first used for partitioning multidimensional M-PSK signal sets [7]. Unfortunately they did not consider CER (Constellation Extension Rate) and PAR (Peak-to-Average power Rate) parameters which are very important in high speed modems. CER is the ratio between average energy of the signal constellation after extension (corresponding to a coded transmission) and the average energy of the signal constellation before extension (corresponding to an uncoded transmission). PAR is the ratio between the peak and the average energy of the signal constellation after extension.

Wang&Costello have presented a method for construction multidimensional TCM codes with shell mapping but only 4-D TCM codes were considered [8].

Sterian has presented a method for the extension of Wei’s construction of 2N-D TCM codes for N being nonpower of 2. He presented as examples 6-D

31

Page 34: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

and 12-D TCM codes but unfortunately he did not consider CER and PAR parameters [10, 12].

Dinh&Hashimoto have presented a method for the construction multidimensional TCM codes based on coset codes [9]. They have constructed multidimensional rectangular signal constellations with optimal (minimum) CER and PAR parameters for constituent 2-D signal constellations.

The advantages of the multidimensional TCM codes over the 2-D TCM codes are the following:

reducing of the loss in coding gain due to the extending of multidimensional signal constellations by reducing the number of redundant bits,

reducing of the size and the CER and PAR parameters for constituent 2-D signal constellations of multidimensional signal constellation,

possibility of transmitting an integral or a nonintegral number of bits in each 2-D signaling interval,

better immunity at phase ambiguities (phase jitter),

better complexity/performance tradeoff. The applications of the multidimesional TCM

codes are: analog voiceband modems, digital wireless modems, digital digital subscriber line (DSL) modems, digital satellite modems.

II. BLOCK DIAGRAM OF THE 2N-D TCM

DECODER

The 2N-D TCM decoder is using a maximum likelihood decoding algorithm (MLD) named Viterbi algorithm (VA) [13].

The Viterbi decoder uses a hard-decision decoding technique and finds the 2N-D signal point which is the closest from the received 2N-D signal point.

The Viterbi decoder contains 2 blocks: ⇒ the computation block that computes for every

2N-D subset the closest 2N-D signal point from the received 2N-D signal point and the associated 2N-D subset metric,

⇒ the Viterbi decoder that analyses the trellis diagram and selects the path with minimum total metric. It generates a sequence of 2N-D signal points which is the closest from the sequence of the received 2N-D signal points. First of all we decompose the received 2N-D

signal point in N constituent 2-D signal point according to the logical diagram presented in Fig.1.

For the Viterbi decoding diagram I (N=nonpower of 2) (Fig.2) the Viterbi decoder is making the following operations:

it finds in each 2-D subset the closest 2-D signal point from each of N received 2-D signal points and it computes the associated 2-D subset metric (the squared Euclidian distance between two 2-D signal points).

for each 2N-D type it computes the 2N-D type metric as sum of N 2-D subset metrics.

for each 2N-D subset it compares the S previous 2N-D type metrics and the smallest metric become the 2N-D subset metric associated with that 2N-D subset. The 2N-D signal point which corresponds to the 2N-D type with the smallest 2N-D type metric become the closest 2N-D signal point from the received 2N-D signal point.

it extends trellis paths and generates final decision about the received 2N-D signal point.

Fig.1 The logical diagram for choosing the Viterbi decoding diagram.

For Viterbi decoding diagram II (N=power of 2) (Fig.3) the Viterbi decoder is making the following operations:

it finds in each 2-D subset the closest 2-D signal point from each of N received 2-D signal points and it computes the associated 2-D subset metric (the squared Euclidian distance between two 2-D signal points).

for each 4-D type it computes the 4-D type metric as sum of 2 2-D subset metrics.

for each 4-D subset it compares the 2 previous 4-D type metrics and the smallest metric become the 4-D subset metric associated with that 4-D subset. The 4-D signal point which corresponds to the 4-D type with the smallest 4-D type metric become the closest 4-D signal point from the first received 4-D signal point (the first and the second 2-D signal points received).

This procedure is repeated for all the 2N

received 4-D signal points. …………………………………….……………... for each 2N-D type it computes the 2N-D

type metric as sum of 2 N-D subset metrics. for each 2N-D subset it compares the S

previous 2N-D type metrics and the smallest metric become the 2N-D subset metric associated with that 2N-D subset. The 2N-D signal point which corresponds to the 2N-D type with the smallest 2N-D type metric become the closest 2N-D signal point from the received 2N-D signal point.

YES NO

YES NO

NO YES

N/2i=1

N/2i= =even

i=i+1

Diagram I

Diagram II

N= =even

N,i=1

32

Page 35: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

it extends trellis paths and generates final decision about the received 2N-D signal point.

If we take into account the boundary effect of a 2N-D signal constellation with a finite number of 2N-D signal points it is necessary that the final decision about the received 2N-D signal point to be a valid signal point of the 2N-D signal constellation which means it contain at most one 2-D signal point from OG.

In the 2N-D TCM decoder after the Viterbi decoder follows N 2-D mapping blocks, 1 bit converter, 1 differential decoder and 1 block decoder which achieve inverse operations from coding.

The relations between the outputs and the inputs of the differential encoder are:

⎪⎪⎩

⎪⎪⎨

′⊕′=

′⊗′⊕′⊕

⊕′⊕′=

+−+−+−

+−+−+−

+++

)II( I

]I)II([

)II( I

N-bn,1abn,1abn,1a

N-bn,1aN-bn,1abn,1a

N-bna,bna,bna,

(1) The block diagram of the 2N-D TCM decoder is presented in Fig.4.

ACKNOWLEDGEMENT

The author would like to thank the professor Miranda NAFORNIŢĂ and the professor Ioan NAFORNIŢĂ from Faculty of Electronics and Telecommunications Timişoara for their encouragement and guidance in preparing his paper.

REFERENCES 1. G. UNGERBOECK -„Channel coding with multilevels/phase signals”-IEEE Trans. Inf. Theory, Vol. IT-28, No. 1, pag. 56-67, Jan. 1982 2. G. D. FORNEY Jr., R. G. GALLAGER, G. R. LANG, F. M. LONGSTAFF, S. U. QURESHI -„Efficient modulation for bandlimited channels”-IEEE J. Select. Areas. Comms, Vol. SAC-2, No. 5, pag. 632-647, Sept. 1984 3. L. -F. Wei „Trellis-Coded Modulation with multidimensional constellations”-IEEE J. Trans. Inf. Theory, Vol. IT-33, No. 4, pag. 483-501, July. 1987 4. G. D. FORNEY Jr. -„Geometrically uniform codes”, IEEE Trans. Inf. Theory, Vol. IT-37, No. 9, pag. 1241-1260, Sept. 1991 5. A. R. Calderbank, N. J. A. Sloane -„Four-dimensional modulation with eight-state trellis code”, AT&T Tech. Journal, Vol. 64, pag. 1005-1018, May/June 1985 6. S. S. PIETROBON , D. J. COSTELLO -„Trellis coding modulation with multidimensional QAM signals sets”, IEEE Trans. Inf. Theory, Vol. IT-39, No. 3, pag. 325-336, Mar. 1993 7. S. S. PIETROBON, R. H. DENG, A. LAFANACHERE, G. UNGERBOECK, D. J. COSTELLO -„Trellis-coded multidimensional phase modulation”, IEEE Trans. Inf. Theory, Vol. IT-36, No. 3, pag. 63-89, Jan. 1990 8. F. Q. WANG, D. J. COSTELLO -„New rotationally invariant four-dimensional trellis codes”, IEEE Trans. Inf. Theory , Vol. IT-42, pag. 291-300, Jan. 1996 9. T. C. DINH, T. HASHIMOTO -„A systematic approach to construction of bandwith-efficient multidimensional trellis codes”, IEEE Trans. Comms., Vol. 48, No. 11, Nov. 2000 10. C. -E. D. STERIAN -„Extending Wei’s trellis coded modulation technique with 2N-D rectangular constellation for N not a power of 2”, Telecomunicaţii, Anul XXI, Nr. 4, 1994 11. C. -E. D. STERIAN -„128-state, rate-4/5 rotationally invariant trellis code with 4-D rectangular signal constellation having a coding gain of 5,63 dB”, Telecomunicaţii, Anul XXIII, Nr. 2, 1996 12. C. -E. D. STERIAN -„Wei-type trellis-coded modulation with 2N-dimensional rectangular constellation for N not a power of 2”, IEEE Trans. Inf. Theory, Vol. IT-43, No. 3, pag. 750-758, Mar. 1997. 13. G. D. FORNEY Jr. -„The Viterbi Algorithm”-IEEE Proc., Vol. 61, pag. 268-278, 1973.

33

Page 36: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Fig.2 The Viterbi decoding diagram I.

1 2 N-1 N

Find the closest N-D signal point in each N-D subset and compute

the associated N-D subset metric

Find the closest N-D signal point in each N-D subset and compute

the associated N-D subset metric

N=odd

N/2=odd

N/4=odd

Find the closest 2N-D signal point in each

2N-D subset and comute the associated 2N-D subset metric

Extend the trellis paths and generate the final

decision about the received 2N-D signal

point

Received 2N-D signal point

Received N-D signal

Received N/2-D signal

Received N/2-D signal

Received N-D signal

Received N/2-D signal

Received N/2-D signal

1 2

1 2 3 4

Received 2-D signal point

Received 2-D signal point

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Received 2-D signal point

Received 2-D signal point

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

34

Page 37: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Fig.3 The Viterbi decoding diagram II.

2

2 3 4

1

1

1

1

N/2

2 N-1 N

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Received 2N-D signal point

Extend the trellis paths and generate the final

decision about the received 2N-D signal

point

Find the closest N-D signal point in each N-D subset and compute

the associated N-D subset metric

Find the closest N-D signal point in each N-D subset and compute

the associated N-D subset metric

Find the closest 2N-D signal point in each

2N-D subset and compute the associated

2N-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Find the closest N/2-D signal point in each

N/2-D subset and compute the

associated N/2-D subset metric

Received 2-D signal point

Received 2-D signal point

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Received 4-D signal point

Received 2-D signal point

Received 2-D signal point

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Find the closest 2-D signal point

in each 2-D subset and

compute the associated 2-D subset metric

Received 4-D signal point

Received N-D signal point

Received N-D signal point

Received N/2-D signal point

Received N/2-D signal point

Received N/2-D signal point

Received N/2-D signal point

35

Page 38: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Fig.4. The block diagram of the 2N-D TCM decoder.

36

Page 39: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar
Page 40: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar
Page 41: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar
Page 42: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar
Page 43: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

41

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 46(60), Fascicola 2, 2001

Propagarea identificatorilor de securitate în apeluri EJB* efectuate din container de servlet cu

implementare Single-Sign-On

Florin Vancea1, Codruţa Vancea2

* EJB – Enterprise JavaBeansTM. Toate denumirile rezervate din text sunt proprietatea organizaţiilro şi entităţilor respective, chiar dacă nu vom marca în mod explicit acest lucru, datorită nevoii de claritate. 1 Universitatea din Oradea, Facultatea de Electrotehnică şi Informatică, Armatei Române 5, 3700 Oradea, e-mail: [email protected] 2 Universitatea din Oradea, Facultatea de Electrotehnică şi Informatică, Armatei Române 5, 3700 Oradea, e-mail: [email protected]

Rezumat - Aplicaţiile web distincte care rulează într-un container de servlet pot să evite reautentificarea utilizatorului pentru a oferi un confort sporit de exploatare. Facilitatea este referită uzual ca “Single-Sign-On” (SSO, autentificare unică). Dacă aplicaţiile web apelează la un mediu EJB în cursul funcţionării, apelurile trebuie să folosească obligatoriu un identificator de securitate. Lucrarea discută diferite politici de efectuare a acestor apeluri din punct de vedere al acestui identificator de securitate, pentru cazul în care containerul de servlet foloseşte SSO. Se fac referiri particulare la cazul pachetului open-source JBoss - Tomcat. Cuvinte cheie: container, servlet, EJB, propagare, JBoss, Tomcat

I. INTRODUCERE

Aplicaţiile prezentate către utilizator prin intermediul interfeţelor web au cunoscut şi cunosc un interes sporit, datorită tendinţei de globalizare a comunicării şi serviciilor informatice. Una din tehnologiile folosite pentru a realiza astfel de aplicaţii este tehnologia servlet, bazată pe conceptele Java [1]. In accepţiunea tehnologiei J2EE, o aplicaţie web este un set de fişiere-resursă (HTML, imagini, altele) şi cod (sub formă de pagini JSP, componente servlet sau clase-suport) însoţite de descrierea modului în care trebuie rulate şi/sau servite către client. Un servlet este o componentă web (de fapt o clasă Java) care rulează în interiorul unui container. Un container este o parte a unui server web sau a unui server de aplicaţie. Rolul său este de a trata traficul intrare/ieşire şi de a gestiona ciclul de viaţă a elementelor conţinute (servlet-uri). Intr-un container pot să coexiste mai multe aplicaţii web şi fiecare este responsabilă de tratarea unui sub-spaţiu distinct din întregul spaţiu de URL-uri

deservite de server. Pentru decuplarea mediului în care funcţionează fiecare aplicaţie web containerul creează câte un context separat. Contextul descrie mediul în care funcţionează servlet-urile unei aplicaţii şi este creat pe baza descrierilor parte a aplicaţiei însăşi. Una din dimensiunile pe care trebuie să le acopere un context este cea de securizare a acceselor la facilităţile aplicaţiei. Pentru a asigura mediul de securitate necesar rulării aplicaţiilor, container-ul trebuie să asigure autentificarea utilizatorilor, controlul accesului şi confidenţialitatea datelor. Autentificarea poate fi făcută prin diferite metode (HTTP basic, HTTP digest, pe bază de form-uri şi pe bază de autentificare-client HTTPS)[2]. Singura metodă prin care server-ul deţine control asupra duratei de viaţă a autentificării este cel bazat pe form-uri. Mecanismul de autentificare pe bază de form-uri implică un dialog form-POST-reply declanşat de container atunci când se detectează o solicitare către un subspaţiu al adreselor URL cu restricţii de acces. Descrierea restricţiilor de acces se face la nivelul fişierelor de configurare parte a aplicaţiilor. Pentru implementarea metodei de autentificare prin form-uri este esenţială capabilitatea de construcţie a unui obiect sesiune, care se stochează pe server şi capabilitatea de a lega diferitele solicitări HTTP ale unui utilizator de acelaşi obiect sesiune. Obiectele sesiune sunt deţinute de contextul în care rulează o anumită aplicaţie, deci autentificarea este în mod normal valabilă pe domeniul unei singure aplicaţii. Intr-o implementare simplă a acestor concepte, utilizatorul trebuie aşadar să se re-autentifice către fiecare aplicaţie cu care interacţionează, chiar dacă aplicaţiile rezidă pe acelaşi server. Specificaţia tehnologiei servlet versiunea 2.3 cere însă container-ului să fie capabil să refolosească identitatea deja

Page 44: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

42

cunoscută a unui utilizator pentru re-autentificarea automată în alte aplicaţii. Mecanismul este numit Single-Sign-On (SSO – autentificare unică) şi presupune stabilirea unor elemente de tip jeton propagate cu fiecare solicitare şi care permit server-ului să identifice utilizatorul indiferent de aplicaţia pe care o foloseşte [3].

II. MEDIUL DE SECURITATE PENTRU EJB

Aplicaţiile web pot să deservească solicitările clienţilor direct sau pentru cazuri mai complicate să facă apel la entităţi şi resurse externe container-ului de servlet. O soluţie arhitecturală pentru cazurile mai complicate este folosirea unui server de aplicaţie, care implementează logica fundamentală a aplicaţiei (business logic). Intr-o astfel de configuraţie, server-ul web şi container-ul de servlet au rolul de prezentare a rezultatelor şi rutare a solicitărilor iar server-ul de aplicaţie execută prelucrările propriu-zise. Aceeaşi specificaţie [4] care introduce între altele mecanismul de servlet defineşte şi un mediu de prelucrare orientat către logica fundamentală a unei aplicaţii, şi anume conceptul de Enterprise JavaBeans (EJB) şi mediul în care funcţionează acestea [5]. Un EJB este reprezentat de o clasă Java construită după un set special de reguli (bean) şi este destinat să încapsuleze într-un mod portabil şi flexibil o anumită funcţie într-un sistem informatic integrat. EJB-urile funcţionează în interiorul unui containerEJB. Acest container tratează accesele clienţilor (în sens informatic) la EJB-uri, gestionează ciclul de viaţă al EJB-urilor pe care le conţine şi intermediază acestora accesul optimizat la resurse generice (baze de date, sisteme de naming, alte resurse). Există mai multe tipuri de EJB, după modul în care îşi îndeplinesc funcţia şi după rolul lor în lanţul de deservire a unei solicitări, dar din punct de vedere al cerinţelor de securitate pe care le discutăm toate au o comportare similară. Specificaţia permite creerea unui mediu securizabil de execuţie pentru EJB-uri, atât la nivel declarativ cât şi la nivel programatic. Accesele la metodele expuse ale EJB-urilor pot fi supuse unor verificări de securitate. Pentru a defini contextul de securitate în care se efectueaza un astfel de apel se folosesc aceleaşi concepte ca şi în cazul aplicaţiilor web şi anume identitatea utilizatorului, reprezentată de un identificator de securitate de tip java.security.Principal dotat cu roluri. La nivel declarativ execuţia unei metode protejate este condiţionată de prezenţa unui anumit rol în setul de roluri pe care îl deţine identificatorul de securitate. Metoda declarativă este metoda recomandată deoarece permite o flexibilitate mai mare şi o refolosire mai uşoară a componentelor EJB. Există însă şi posibilitatea implementării programatice a unei politici de securitate, bazate tot pe roluri dar a căror verificare nu se face de container ci de codul din EJB-ul însăşi. Autentificarea apelantului şi producerea identificatorilor de securitate se face în contextul unuia sau mai multor domenii de securitate care pot fi

întreţinute de container sau pot fi în exterior (de exemplu Kerberos).

III. PROPAGAREA IDENTIFICATORILOR DE SECURITATE ÎN RELAŢIA SERVLET-EJB

Dacă un servlet are nevoie să efectueze un apel la o entitate EJB pentru îndeplinirea sarcinilor sale şi dacă metoda apelată este protejată atunci servlet-ul trebuie să furnizeze împreună cu apelul un identificator de securitate valid. In funcţie de specificul aplicaţiei se pot adopta următoarele politici de construcţie a acestui identificator de securitate [6]:

(a) identificatorul original construit de containerul de servlet este propagat spre containerul de EJB

(b) se construieşte un identificator unic pentru orice apel şi acesta este propagat spre containerul de EJB (politică “run-as”)

Identificatorul de securitate conţine descrierea identităţii apelantului şi rolurile asociate dar nu conţine mijloace de reautentificare. Autentificarea se consideră a fi făcută deja de către apelant şi între containerul de servlet şi containerul de EJB există o relaţie implicită de încredere. Putem distinge două situaţii legate de modul de implementare şi de localizarea celor două containere implicate:

1. containerul de servlet şi containerul de EJB funcţionează în aceeaşi maşină virtuală Java. In mod natural, identificatorul de securitate se referă la acelaşi domeniu iar propagarea sa este directă. Apelurile sunt în mod normal locale, deşi pot fi folosite şi apeluri distante.

2. containerul de servlet şi containerul de EJB funcţionează în maşini virtuale Java diferite (în mod normal pe maşini fizice diferite). In acest caz, apelurile trebuie să fie distante iar containerul de servlet trebuie să dispună de mediul care îi permite să funcţioneze ca un client al containerului de EJB. Propagarea identificatorilor de securitate se face printr-o eventuală conversie la trecerea din codul de servlet în codul-client al containerului de EJB. După această eventuală conversie, codul client al containerului de EJB propagă prin metode proprii identificatorul de securitate obţinut pentru a executa metoda în urma unui apel distant la containerul de EJB propriu-zis. Codul client al containerului de EJB funcţionează ca un proxy pentru containerul propriu-zis.

Metoda 2. permite o plasare distribuită a celor două conatinere şi chiar folosirea unor domenii de securitate diferite, prin combinarea cu politica “run-as”.

IV. IMPLEMENTAREA JBOSS – TOMCAT

JBoss este un server de aplicaţie open-source extrem de popular, atât datorită considerentelor legate de cost cât şi datorită performanţelor. La nivelul codului client, construcţia identificatorului de securitate

Page 45: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

43

pentru apelurile la metode protejate ale EJB-urilor conţinute se face conform specificaţiilor JAAS (Java Autenthication and Authorization Service) [7], folosind metode callback pentru obţinerea parametrilor de securitate de la utilizator (nume, parolă). Coordonatele sunt verificate în contextul unui Realm (domeniu) care este flexibil configurabil spre o sursă internă sau spre o sursă externă de autentificare. In urma verificării cu succes se contruieşte un identificator de securitate care se stochează în variabile locale firului de execuţie în care se derulează apelul. In acest fel, coordonatele de securitate sunt asociate apelului şi pot fi accesate pe durata procesării acestuia în vederea efectuării verificărilor declanşate de securitatea declarativă sau pentru atingerea securităţii prin metode programatice, în interiorul EJB-urilor. Una din variantele în care este distribuit JBoss foloseşte ca şi front-end pentru aplicaţii web containerul de servlet open-source Jakarta Tomcat. Autentificarea utilizatorilor se face faţă de un domeniu, prezentat în mod flexibil sub forma unei interfeţe Realm. Containerul Tomcat furnizează direct câteva implementări de Realm pentru sursele comune de autentificare dar utilizatorul poate să configureze propria sa implementare de Realm pentru a atinge scopuri speciale. Pentru a integra containerul de servlet cu serverul de aplicaţie trebuie rezolvată între altele şi problema propagării identificatorilor de securitate din contextul containerului de servlet în contextul containerului de EJB din interiorul serverului de aplicaţie. La combinaţia JBoss - Tomcat soluţia este configurarea în Tomcat a unei implementări speciale de Realm (clasa JBossSecurityMgrRealm) care face finalmente apel la sursa de securitate (de fapt la domeniul de securitate) configurat în JBoss însăşi. La momentul prezentării unei solicitări spre Tomcat care necesită autentificare, mecanismele interne Tomcat bazate pe o stivă de preprocesoare (numite Valve [3]) accesează Realm-ul care este cel furnizat de JBoss. La apelare, pe lângă autentificarea propriu-zisă, clasa asociază identitatea obţinută a utilizatorului cu firul de execuţie curent, aşa încât apelurile care le va efectua servlet-ul să deţină deja identitatea necesară. Deoarece firele de execuţie sunt grupate într-un arie de refolosire (pool) şi sunt refolosite pentru procesarea următoarelor solicitări, identitatea trebuie de-asociată după terminarea procesării. Operaţia este realizată tot de JBossSecurityMgrRealm, în calitatea sa de implementare a interfeţei Valve. Clasa este inserată în stiva de preprocesoare şi astfel are ocazia să execute operaţia inversă asocierii descrise mai sus, eliberând firul de execuţie de “încărcătura” sa de identificare. Trebuie observat că integrarea nu este complet transparentă relativ la modul de configurare a containerului de servlet. Tomcat permite eficientizarea acceselor prin manevre de memorare şi refolosire (cache) aplicate asupra identificatorului de securitate obţinut de la un Realm. Funcţionarea corectă a mecanismului descris necesită ca fiecare acces autentificat care face apel la EJB-uri să treacă prin Realm-ul furnizat, altfel asocierea

identificatorului de securitate cu firul de execuţie nu se execută şi apelul la EJB nu va avea identificatorul de securitate necesar.

V. UTILIZAREA SSO ÎN JBOSS – TOMCAT

Problema descrisă mai sus se rezolvă prin interzicerea aplicării unei politici de cache, obligând fiecare apel autentificat să producă şi asocierea necesară. Totuşi, în cazul în care containerul de servlet este configurat să folosească SSO, există un mecanism de cache intrinsec, destinat să producă automat identificatori de securitate pentru toate aplicaţiile web din container în cazul în care sesiunea respectivului utilizator s-a autentificat deja în una din aplicaţii. Consecinţa acestui comportament asupra combinaţiei JBoss - Tomcat cu Tomcat configurat pentru SSO este că apelurile efectuate în aplicaţia în care s-a făcut efectiv autentificarea primesc un identificator de securitate corect şi apelurile către EJB-uri pot să se deruleze normal. In celelalte aplicaţii în schimb, solicitările sunt automat asociate cu identificatorul de securitate deja obţinut şi nu mai e nevoie de un acces la Realm (în cazul nostru JBossSecurityMgrRealm), deci asocierea firului de execuţie cu identificatorul corect de securitate nu se mai face iar apelurile la EJB-uri nu vor reuşi.

VI. SOLUŢII PROPUSE

Pentru corectarea acestui comportament am încercat diverse soluţii, descrise în continuare.

1. Modificarea comportamentului preprocesorului de tip Valve care asigură comportamentul SSO din Tomcat. Din păcate această soluţie este dificil de implementat, pentru că mecanismul SSO la Tomcat este distribuit de fapt între procesorul de SSO şi procesoarele automat introduse de container în funcţie de tipul de autentificare solicitat în descriptorul aplicaţiei. Modificarea ar presupune înlocuirea întregului ansamblu, aşa încât o reîmpachetare ar fi necesară şi mai mult, pentru a aplica soluţia la următoarea versiune a containerului operaţia ar trebui repetată.

2. Modificarea mecanismului de integrare între JBoss şi Tomcat prin introducerea unui preprocesor suplimentar, care să efectueze operaţia de asociere între identitatea obţinută deja şi firul de execuţie. Soluţia s-a dovedit la fel de dificil de implementat, deoarece Tomcat este pornit ca un serviciu din interiorul server-ului de aplicaţie iar configuraţia sub care porneşte este generată dinamic de JBoss. Introducerea unui preprocesor suplimentar trebuie făcută după preprocesoarele automat configurate din descriptorul de aplicaţie pentru că abia acolo este disponibil identificatorul de securitate corect.

3. Inlocuirea preprocesoarelor de securitate configurate automat de Tomcat din descriptorul aplicaţiei web cu clase externe care să apeleze la clasele originale pentru efectuarea operaţiilor standard şi să adauge un apel (redundant din

Page 46: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

44

punct de vedere al aplicaţiei web) la implementarea de Realm oferită de JBoss, asigurând asocierea corectă a identificatorului de securitate cu firul de execuţie. Această soluţie este cea mai avantajoasă, pentru că are un grad minim de intruziune în mecanismele existente şi are cele mai mari şanse să reziste în faţa unor versiuni noi fără necesitatea unor ajustări în codul sursă al celor două componente.

Implementarea soluţiei 3 nu este lipsită de probleme. Deşi preprocesoarele automat configurate din descriptorul aplicaţiei sunt alese de Tomcat pe baza unui fişier de configurare, acesta este inclus în pachetul-arhivă al aplicaţiei şi modificarea ar necesita despachetarea, inlocuirea configuraţiei şi reîmpachetarea pentru fiecare nouă versiune folosită. In acelaşi timp, o astfel de soluţie ar împiedica exploatarea “ca atare” a unei distribuţii de JBoss - Tomcat obţinută direct prin Internet. Soluţia găsită este un artificiu care se bazează pe modul de încărcare al resurselor de tip proprietăţi. La încărcarea unui set de proprietăţi o clasă cu numele specificat are prioritate asupra unui fişier “.properties”, aşa că am creat o clasă derivată din ListResourceBundle, care conţine varianta noastră de configurare. Prin plasarea acestei clase în calea de încărcare înaintea arhivelor originale ale aplicaţiei putem forţa modificarea configuraţiei fără să ne atingem de distribuţia originală. O altă problemă este modalitatea de derivare a propriei clase de preprocesare din clasele originale. Din păcate, unele metode strict necesare pentru atingerea scopurilor noastre de interfaţare sunt private în definiţiile originale ale claselor, deci am fost nevoiţi să reimplementăm o parte din funcţionalitatea claselor originale. Ca o observaţie, deşi în versiunea de JBoss pe care am lucrat JBossSecurityMgrRealm implementează şi interfaţa Valve destinată să elibereze asocierea între firul de execuţie şi identificatorul de securitate, ea nu este inclusă în configuraţia de Tomcat generată, deci deasocierea nu se execută. Efectul este catastrofal pentru securitate deoarece firul de execuţie este refolosit la următoarea solicitare şi o va executa în contextul de securitate a primului apelant. Problema se rezolvă prin introducerea lui JBossSecurityMgrRealm ca preprocesor în stiva configuraţiei Tomcat folosite.

VII. CONCLUZII

Ansamblul container de servlet / container EJB oferă un mediu puternic pentru dezvoltarea şi rularea unor aplicaţii complexe, organizate într-un mod structurat şi cu o mare flexibilitate. Prezenţa unor astfel de componente în regim open-source facilitează pătrunderea acestor tehnologii şi permite perfecţionarea funcţionării lor în situaţii complexe. Am identificat o problemă de securizare existentă într-o anumită configuraţie a combinaţiei open-source JBoss - Tomcat şi am oferit o soluţie de rezolvare care să afecteze cât mai puţin distribuţia originală, în

dorinţa de a minimiza necesitatea abilităţilor de re-compilare şi re-configurare în aplicarea acestei soluţii. In spiritul open-source soluţia în formă de surse este disponibilă celor interesaţi, momentan doar prin contactarea directă autorilor.

BIBLIOGRAFIE

[1] Java Servlet Specification, version 2.3, Sun Microsystems, 2001 [2] J. Franks, P. Hallam-Baker, J. Hostetler, S. Lawrence, P. Leach, A. Luotonen, E. Sink, L. Stewart, “HTTP Authentication: Basic and Digest Access Authentication”, RFC 2617, June 1999 [3] F. Vancea, C. Vancea, “Single-Sign-On Issues in Web-Based Applications”, EMES-2003, Oradea 2003 [4] Java 2 Platform Enterprise Edition Specification, version 1.3, Sun Microsystems, 2001 [5] Enterprise JavaBeans(TM) Specification, version 2.0, Sun Microsystems, 2001 [6] S. Bodoff, D. Green, K. Haase, E. Jendrock, M. Pawlan, B. Stearns, “The J2EE Tutorial”, Addison-Wesley, March 2002, ISBN 0-201-79168-4 [7] C. Lai, L. Gong, L. Koved, A. Nadalin, R. Schemers, “User Authentication and Authorization in the Java(TM) Platform”, Proceedings of the 15th Annual Computer Security Applications Conference, Phoenix, AZ, December 1999, disponibil şi online la http://java.sun.com/security/jaas/doc/acsac.html

Page 47: Redactor Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurc · Conf. dr. ing. Dorina Isar Prof. dr. ing. Traian Jurcă Conf. dr. ing. Aldo De Sabata As. ing. Kovaci Maria - secretar

Buletinul Ştiinţific al Universităţii "Politehnica" din Timişoara

Seria ELECTRONICĂ şi TELECOMUNICAŢII TRANSACTIONS on ELECTRONICS and COMMUNICATIONS

Tom 47(61), Fascicola 1, 2002

Instrucţiuni de redactare a articolelor pentru Buletinul ştiinţific al Facultăţii de Electronică şi Telecomunicaţii

Gheorghe I. Popescu1

1 Facultatea de Electronică şi Telecomunicaţii, Departamentul Comunicaţii Bd. V. Pârvan Timişoara 1900 e-mail [email protected]

Rezumat – Aceste instrucţiuni sunt concepute să vă prezinte modul de redactare al articolelor pentru Buletinul ştiinţific al Facultăţii de Electronică şi Telecomunicaţii. Prezentul material este conceput ca model pentru modul cum trebuie să arate articolele gata de publicare. Rezumatul trebuie să conţină descrierea problemei, metodele şi soluţiile propuse şi rezultatele experimentale obţinute în cel mult 12 rânduri. Nu se admit referinţe bibliografice în cadrul rezumatului. Cuvinte cheie: redactare, buletin ştiinţific

I. INTRODUCERE

Formatul buletinului va fi A4. Articolele, inclusiv tabelele şi figurile, nu trebuie să depăşească 6 pagini. Numărul de pagini trebuie să fie obligatoriu par.

II. INSTRUCŢIUNI DE REDACTARE

Articolul trebuie să fie transmis în forma standard descrisă în acest material. Tipărirea se va face cu o imprimantă de bună calitate pe o singură faţă a paginii. Textul se va plasa pe două coloane de 8 cm cu spaţiu de 0,5 cm între ele. Pagina A4 orientată pe înălţimea paginii are marginile de sus şi jos de 1,78 cm, iar cele din stânga şi dreapta de 2,54 cm. Prima pagină a articolului va avea marginea superioară de 5 cm. Pentru editarea articolului se recomandă utilizarea procesorului de text Microsoft Word for Windows cu caractere Times New Roman dactilografiate la un rând. Dimensiunile şi stilul caracterelor sunt: Titlul articolului 18 pt îngroşat, autorul 12 pt rezumatul 9 pt îngroşat, cuvintele cheie 9 pt îngroşat, titlu paragraf 10 pt majuscule, titlu subparagraf 10 pt italic, distanţa de la numărul de ordine la titluri va fi de 0,25 cm, textul normal 10 pt, afilierea autorului 8 pt, notele de subsol 8 pt, legendele figurilor 8 pt şi bibliografia 8 pt.

III. FIGURI ŞI TABELE Figurile şi tabelele trebuiesc inserate în text aliniate la stânga. Se recomandă evitarea plasării figurilor înainte de prima lor menţionare în text. Se va folosi abrevierea “Fig.1.” chiar şi la începutul propoziţiilor. Ecuaţiile

trebuie tipărite cu un rând gol deasupra şi dedesubt. Numerotarea lor se face simplu în paranteze: (1), (2), (3) … Numerotarea va fi aliniată faţă de marginea dreaptă.

IV. REFERINŢE BIBLIOGRAFICE Referinţele bibliografice se numerotează consecutiv în forma [1], [2], [3]… Citările se fac simplu prin plasarea numărului corespunzător [5]. Nu sunt permise referinţe bibliografice în notele de referinţă în subsol. Se recomandă scrierea tuturor autorilor şi nu folosirea expresiei “şi alţii” decât dacă sunt peste 6 autori.

V. SFATURI UTILE A. Abrevieri şi acronime Explicitaţi abrevierile şi acronimele prima dată când ele apar în text. Abrevieri precum IEEE, IEE, SI, MKS, CGS, ac, dc şi rms se consideră cunoscute şi nu mai trebuie explicitate. Nu se recomandă utilizarea abrevierilor în titluri decât în cazul când sunt absolut inevitabile. B. Alte recomandări Se recomandă utilizarea unităţilor de măsură din sistemul internaţional. Utilizarea unităţilor britanice poate fi făcută doar ca unităţi secundare (în paranteză). Se va evita combinarea unităţilor SI şi CGS. Nu se admit rezultate experimentale preliminare. Numerotarea cu cifre romane a titlurilor de paragrafe este opţională. În cazul utilizării acestora se vor numerota paragrafelor propriu-zise şi nu “BIBLIOGRAFIA” sau “MULŢUMIRI”.

BIBLIOGRAFIE [1] A. Ignea, “Preparation of papers for the International Sympozium Etc. ’98”, Buletinul Universităţii “Politehnica” Tom 43 (57), 1998, Fascicola 1, 1998, pp. 81