Heugas A-M Lina Majed
email: lina.majed@u-psud.fr

Anne-Marie Heugas

Marcella Chamon

Isabelle Siegler

Learning an energy

Keywords: Motor learning, Multisegment movement, Metabolic efficiency, Perceived exertion, Racewalking

come   L'archive ouverte pluridisciplinaire

Introduction

A large number of studies on motor learning focused on understanding the process of passing from a novice status to increased levels of expertise when learning a complex motor task involving a large number of degrees of freedom. Investigators proposed a variety of global motor tasks that involve whole body segments, such as postural coordination tasks on a ski simulator [START_REF] Vereijken | Changing coordinative structures in complex skill acquisition[END_REF][START_REF] Almasbakk | The efficient learner[END_REF][START_REF] Hong | Change in the organization of degrees of freedom with learning[END_REF], a moving platform [START_REF] Ko | Learning to coordinate redundant degrees of freedom in a dynamic balance task[END_REF][START_REF] Teulier | The nature of the transition between novice and skilled coordination during learning to swing[END_REF] or a stabilometer [START_REF] Caillou | Overcoming spontaneous patterns of coordination during the acquisition of a complex balancing task[END_REF]. The learning process was also examined in many sporting activities like rowing an ergometer [START_REF] Sparrow | Effects of practice and preferred rate on perceived exertion, metabolic variables and movement control[END_REF][START_REF] Lay | Practice effects on coordination and control, metabolic energy expenditure, and muscle activation[END_REF], swimming the butterfly stroke [START_REF] Seifert | Differences in spatial-temporal parameters and arm-leg coordination in butterfly stroke as a function of race pace, skill and gender[END_REF] or the breast-stroke [START_REF] Seifert | Inter-limb coordination in swimming: effect of speed and skill level[END_REF], the triple jump [START_REF] Wilson | Coordination variability and skill development in expert triple jumpers[END_REF] or the hand stand in gymnastics [START_REF] Gautier | Dynamics of expertise level: Coordination in handstand[END_REF]. Inspired by Bernstein's proposals (1967) about the mastery of multiple and redundant degrees of freedom with motor learning, many of the above authors aimed at understanding movement reorganization by studying limb and body kinematics [START_REF] Vereijken | Changing coordinative structures in complex skill acquisition[END_REF][START_REF] Caillou | Overcoming spontaneous patterns of coordination during the acquisition of a complex balancing task[END_REF][START_REF] Ko | Learning to coordinate redundant degrees of freedom in a dynamic balance task[END_REF][START_REF] Hong | Change in the organization of degrees of freedom with learning[END_REF][START_REF] Seifert | Differences in spatial-temporal parameters and arm-leg coordination in butterfly stroke as a function of race pace, skill and gender[END_REF][START_REF] Wilson | Coordination variability and skill development in expert triple jumpers[END_REF][START_REF] Gautier | Dynamics of expertise level: Coordination in handstand[END_REF][START_REF] Seifert | Inter-limb coordination in swimming: effect of speed and skill level[END_REF]. It's only in a few studies that authors, inspired by the metabolic optimization theory [START_REF] Sparrow | The efficiency of skilled performance[END_REF], also examined energetic and perceived exertion factors in an attempt to establish a link between movement reorganization, metabolic efficiency [START_REF] Almasbakk | The efficient learner[END_REF][START_REF] Lay | The metabolic and cognitive energy costs of stabilising a high-energy interlimb coordination task[END_REF] and perceived exertion [START_REF] Sparrow | Effects of practice and preferred rate on perceived exertion, metabolic variables and movement control[END_REF][START_REF] Lay | Practice effects on coordination and control, metabolic energy expenditure, and muscle activation[END_REF].

From a dynamical point of view, movement reorganization with motor learning is viewed as self-organized [START_REF] Kelso | Dynamic patterns: the self-organization of brain and behavior[END_REF][START_REF] Kugler | Information, natural laws, and the selfassembly of rhythmic movements[END_REF]. New patterns emerge as a function of the demands arising from the constraints imposed by the organism, the task, and the environment [START_REF] Newell | Constraints on the development of coordination[END_REF]. This approach offers methods of analysis to study the evolution of movement patterns on a macroscopic scale. In motor learning, evidence of selforganization can be understood in terms of strategies used in establishing new coordinative patterns [START_REF] Bernstein | The co-ordination and regulation of movement[END_REF][START_REF] Newell | Coordination, control and skill[END_REF]. [START_REF] Newell | Coordination, control and skill[END_REF] proposed a 3-stage learning model that is still serving as a backdrop for studying complex motor skills learning [START_REF] Chow | Coordination changes in a discrete multi-articular action as a function of practice[END_REF]. In the first stage of this model, referred to as the "coordination" stage, the learner exclusively focuses on the task realization and therefore attempts to establish basic relationships among motor system components in order to achieve functional, goal directed movements. As a consequence, the learner may adopt a rigid behavior. According to [START_REF] Newell | Coordination, control and skill[END_REF], adult learners may progress rapidly to the second stage, the "control" stage, which is the process by which values are assigned to the coordination function, i.e a parametrizing process. This stage is characterized by a decrease of dysfunctional variability resulting in a higher consistency in task realization. Finally, in the third stage of learning referred to as the "skill stage", an optimal adaptation in movement is found emphasizing energy efficiency. This three-stage learning model was completed by evidence of other strategies, derived from developmental studies, such as the proximal to distal release of constrained degrees of freedom [START_REF] Newell | Are Gesell's developmental principles general principles for the acquisition of coordination[END_REF]. However, contradictory results suggest that the emergence of a directional trend in pattern reorganization with motor learning (i.e. proximalto-distal) is not a generalized mechanism [START_REF] Newell | Dimensional change in motor learning[END_REF]. Until now, it is still unclear what common characteristics or general mechanisms are shared when learning a complex motor task. Many conclusions, however, have put forward the important role of task constraints in movement reorganization when learning a complex motor skill [START_REF] Caillou | Overcoming spontaneous patterns of coordination during the acquisition of a complex balancing task[END_REF][START_REF] Ko | Learning to coordinate redundant degrees of freedom in a dynamic balance task[END_REF].

Racewalking is a "biomechanically constrained" task in which the constraints on the limb movements define the task [START_REF] Newell | Constraints on the development of coordination[END_REF]. Racewalking can be distinguished from running by the constraint that one foot has to remain in contact with the ground at all times. When the performer breaks this rule, he/she gains an advantage by being released from this constraint. In addition, the regulation states that the advancing leg has to remain straightened from the moment of its first contact with the ground until its vertical upright position (i.e. IAAF, 1995). By this latter constraint, racewalking can be distinguished from normal walking. In addition to its high biomechanical constraints, racewalking is also a highly energy-demanding activity [START_REF] Fougeron | Le coût énergétique de la marche athlétique: évolution en fonction de la vitesse de déplacement[END_REF][START_REF] Hagberg | Physiologic comparison of competitive racewalking and running[END_REF]. Metabolic aspects in this case can play the role of an additional constraint that needs to be considered.

Indeed, in a search for invariant characteristics in complex motor skill learning, one defining characteristic has been attributed to metabolic "efficiency". Increased interest was shown in understanding the energetic process underlying coordination dynamics. It is generally agreed that organisms naturally tend to adopt a movement pattern that minimizes metabolic energy expenditure, as presented in the self-optimization theory [START_REF] Sparrow | The efficiency of skilled performance[END_REF]. Studies examining both metabolic processes and movement reorganization with motor learning, revealed that changes in movement are accompanied with a reduction in metabolic energy expenditure independently of physical conditioning [START_REF] Sparrow | Effects of practice and preferred rate on perceived exertion, metabolic variables and movement control[END_REF][START_REF] Almasbakk | The efficient learner[END_REF][START_REF] Lay | Practice effects on coordination and control, metabolic energy expenditure, and muscle activation[END_REF]. When learning slalom-like ski movements on a ski apparatus, [START_REF] Almasbakk | The efficient learner[END_REF] showed that the changes in movement coordination were paralleled with an improved efficiency. Moreover, Sparrow and colleagues [START_REF] Sparrow | Effects of practice and preferred rate on perceived exertion, metabolic variables and movement control[END_REF][START_REF] Lay | Practice effects on coordination and control, metabolic energy expenditure, and muscle activation[END_REF] reported a significant decrease in ratings of perceived exertion [START_REF] Borg | The increase of perceived exertion, aches and pain in the legs, heart rate and blood lactate during exercise on a bicycle ergometer[END_REF] as a function of practice. In addition to the established correlation between perceived exertion and physiological responses, perceived exertion reflecting central (i.e. oxygen consumption and ventilator drive) and peripheral (i.e. active limb muscles and tissue) stress has been considered as an important indicator in the search for new movement patterns [START_REF] Lay | Practice effects on coordination and control, metabolic energy expenditure, and muscle activation[END_REF].

From this perspective, two hypotheses, originally formulated by [START_REF] Sparrow | Metabolic energy expenditure and the regulation of movement economy[END_REF], can be proposed to understand the link between physiological processes, perceived exertion and movement reorganization. In the first hypothesis, consistent with dynamical system theory, metabolic efficiency is considered a consequence of a more fundamental selforganizing principle in which preferred behaviors emerge from stability considerations. In the second hypothesis, the search for metabolic efficiency is considered a primary stimulus to movement organization and preferred patterns would be adopted on the basis of sensory information regarding metabolic energy expenditure and/or perceived exertion. [START_REF] Lay | The metabolic and cognitive energy costs of stabilising a high-energy interlimb coordination task[END_REF] have recently investigated practice effects when performing a highly energy demanding and intrinsically unstable coordination pattern on a bicycle ergometer. The authors concluded that coordination modes lower in metabolic energy expenditure may compete with dynamically stable modes.

The present experiment was therefore designed to bring additional information about how movement patterns are reorganized with respect to physiological responses and perceived exertion when practicing a complex athletic task highly demanding in energy. The key feature of the present experiment lies in the choice of the motor skill that involves more complex coordination than the previous tasks studied in the literature (i.e. rowing, biking or skiing on ergometers) with segmental rotation in three-dimensions, and especially with the implication of hip rotations in two different planes. Moreover, the analyses will comprise a large number of movement variables accounting for lower/upper body and distal/proximal coordination, and a dissociation between peripheral and central perceived exertion. In the present study, participants were expected to be able to perform 6 minutes of racewalking at 10 km.h -1 on a motor driven treadmill at the 7 th and last learning session. In doing so, the first aim of this study was to examine whether movement in complex motor learning is reorganized following fundamental strategies, proceeding in three globally different stages and following a directional trend from proximal to distal levels. By choosing a highly a biomechanically constrained and energy-demanding task, the second aim of the present study was to gain further insights into the nature of the link between movement reorganization, sensory information and movement economy.

Methods

Participants

Seven healthy, physically fit male volunteers were recruited with no previous experience in racewalking. Informed written consents were provided before testing, in accordance with the guidelines of the Ethical Committee of the University of Paris-Sud. A medical certificate of non contraindication to submaximal effort was required prior to performing the experiment. Participants had a mean age of 23.3 years (SD = 6.4), mean height of 1.79 m (SD = 4.7 cm) and mean weight of 69.1 kg (SD = 7.8 kg). All participants were instructed to adhere to their normal diets throughout the testing procedures and were advised to refrain from caffeine or alcohol preceding the day of testing.

Apparatus

Kinematics were recorded using 8 infra-red emitting cameras connected to VICON movement analysis system (Oxford Metrics, UK) at a sample rate of 60 Hz. Nineteen passive reflective markers were placed, according to plug-in-gait model marker set, on the participant's torso (xiphoid process of the sternum), shoulders (acromio-clavicular joint), elbows (lateral epicondyle), wrists (pinkie side bar), pelvis (anterior superior iliac spines), thighs (exterior lateral lower 1/3 surface), knees (lateral epicondyle), ankles (lateral malleolus), toes (second metatarsal head) and heels (calcaneous). The experiment was performed on a 213 × 90 × 135 cm treadmill (Valiant, Lode, The Netherlands) which had a speed range of 1-25 km.h -1 . The treadmill's long axis represented the antero-posterior axis (X-axis) in the kinematic calibration procedure. The Y and Z axes corresponded to the mediolateral and vertical axes, respectively. Prior to each session, static and dynamic calibrations of the working space were carried out, according to the manufacturer instructions.

The variables characterizing respiratory and pulmonary gas exchange were measured using a portable breath-by-breath gas analyzer (Cortex MetaMax 3B, Germany) with dedicated software (MetaSoft 3.9, Germany). The system was calibrated before each session with room air and reference gases of known concentrations and air flow volume was calibrated with a 3-liter syringe, as recommended by Medbo and collaborators [START_REF] Medbo | Examination of the Metamax I and II oxygen analysers during exercise studies in the laboratory[END_REF]. Heart rate (HR) was monitored throughout the sessions (Polar, Kempele, Finland). Fingertip capillary blood samples were collected and immediately analyzed for blood lactate concentration using a Lactate Pro portable device (Arkray, Japan). Ratings of perceived exertion (RPE) scores were determined using a printed 15 point (6 to 20) graded category scale of perceived exertion [START_REF] Borg | Perceived exertion: A note on "history" and methods[END_REF], placed on a poster background in front of participants.

Protocol

The experiment comprised two preliminary tests and seven racewalking learning sessions (S1-S7). The first preliminary test was a VO 2max determination test and the second consisted in determining the preferred transition speed (PTS) between walking and running. Prior to undertaking the first session, participants were familiarized with treadmill walking and running for at least 30 min. Participants were also familiarized with Borg's scale [START_REF] Borg | Perceived exertion: A note on "history" and methods[END_REF] and instructed how to indicate perceived exertion when requested by the experimenter. Using Borg's scale, participants gave central and peripheral perceived exertion ratings (CPE, PPE). CPE was related to stress on the participants' heart and lungs while PPE concerned the stress on the limbs and joints.

VO 2max test

The initial test velocity was set at 11 km.h -1 and maintained 6 min for warm-up, then increased by 1 km.h -1 every minute. Participants ran on the treadmill (slope of 3%) until volitional exhaustion [START_REF] Léger | A maximal multistage 20m shuttle run test to predict VO2max[END_REF]. Fingertip capillary blood samples were collected before the test, immediately after exhaustion, and after a three-minute recovery period.

Preferred transition speed test

The individual preferred transition speeds (PTS) were assessed with a procedure used in other studies [START_REF] Diedrich | Why change gaits? Dynamics of the walkrun transition[END_REF]. Participants first warmed up by walking and running for 15 min. They were then submitted to 4 randomly given transition trials of 9 min in which treadmill speed was either incremented from 6 km.h -1 (W-R condition) or decremented from 10 km.h -1 (R-W condition) by 0.5 km.h -1 steps every minute. Treadmill velocity was kept constant between the steps and was not revealed to participants. The following instructions were given: "For these trials we will be changing the speed of the treadmill while you are on it. Please use the type of locomotion that feels most comfortable. That is, make the transition when it seems natural to do so" [START_REF] Diedrich | Why change gaits? Dynamics of the walkrun transition[END_REF].

Learning sessions

Participants were submitted to seven racewalking learning sessions each lasting approximately 60 min. All sessions started with a 10 min warm-up at freely chosen speeds. Before each learning session, 3 instructions were repeated to participants: "Instruction #1: The foot contact with the ground should start with the heel; Instruction #2: the advancing leg should remain straight, from the moment of first contact with the ground until the vertical upright position (i.e. IAAF regulation, 1995); Instruction #3: elbows should be flexed". It was strongly emphasized that the final goal of the learning experiment for the participants was to accomplish 6 minutes of racewalking at a speed of 10 km.h -1 .

The treadmill velocities the participants were submitted to during the experiment were chosen relatively to individual PTS values to ensure that there were no metabolic or mechanical discriminatory factors [START_REF] Hanna | Triggers for the transition between human walking and running[END_REF][START_REF] Hreljac | Effects of physical characteristics on the gait transition speed during human locomotion[END_REF]. The first three learning sessions (S1, S2, S3) comprised 4 practice trials during which treadmill velocity was kept constant and moderate. The two first trials lasted 6 minutes and treadmill velocity was set at PTS and PTS+0.5 km.h -1 (PTS+1), respectively. For the two following trials, treadmill velocity was set at PTS+1 km.h -1 (PTS+2) during 4 minutes. From the fourth learning session S4, higher speed practice trials were introduced [PTS+1.5 km.h -1 (PTS+3); PTS+2 km.h -1 (PTS+4)], after participants performed the practice trials at moderate speeds. Therefore, as learning sessions passed, the number of practice trials was augmented, reaching 7 at the last session, allowing participants to practice at all speeds. Between each practice trial, heart rate was monitored to insure that participants had enough recovery time (HR < 120 bpm) in order to avoid fatigue effects. All the learning sessions were separated by a minimum of 24 hours.

Data acquisition and analysis 2.4.1. VO 2max

Gas exchange data, heart rate and respiratory exchange ratio were averaged for the last 30s of each 1-minute velocity plateau, corresponding to a steady state [START_REF] Hagberg | Transient O2 uptake response at the onset of exercise[END_REF]. The criteria used to determine the maximal oxygen uptake (VO 2max ) were: (1) the reach of a plateau or a peak in oxygen uptake values, (2) a respiratory exchange ratio value superior to 1.1, (3) a blood lactate above 8 mmol and (4) a HR ≥ 90% of the predicted HR max (220 -age) [START_REF] Howley | Criteria for maximal oxygen uptake: review and commentary[END_REF].

Preferred Transition Speed

Kinematic data were collected in 30s samples corresponding to the last 10s of each 1minute velocity plateau and the first 20s of the next velocity plateau, in order to be able to assess transition speed, which was expected to occur after a treadmill velocity step. The W-R or R-W transitions were indicated by the absence or presence of a flight phase in gait cycle. PTS was then defined as the average of the four W-R and R-W transition speeds [START_REF] Hreljac | Effects of physical characteristics on the gait transition speed during human locomotion[END_REF]. For the two transition trials in the R-W condition, the 1-minute plateau following the transition and corresponding to normal walking at PTS is analyzed and referred to as S0. Mean movement and physiological data at S0 are used as a reference when assessing the changes occurring at S1 (cf. §2.5).

Movement variables

Kinematic data were collected during learning sessions S1, S4, S6 and S7 in 30s samples in the middle and at the end of each trial (2:00-2:30, 3:30-4:00 min for the 4 min trials and3:00-3:30, 5:30-6:00 for the 6 min trials). Each 30-second acquisition is referred to as a data "collection period". Five collection periods out of the 456 were discarded from the analysis because of marker occlusions.

Data were filtered using a second order Butterworth low pass filter with a 12Hz cut-off frequency. Movement variables were calculated using a personalized MATLAB program (The MathWorks, Natick, USA). A peak-peaking algorithm was used in order to detect maximum (peaks) and minimal (valleys) values of joint angles and segment rotations. A gait cycle was defined from the instant of maximum knee flexion to the next same event. The maximum-knee-flexion event was chosen because it was easily detectable and shared by the three studied locomotion. Movement variables were calculated for each gait cycle, and then, mean and standard deviation values were computed for each collection period.

Three types of movement variables were computed: (1) global gait parameters, (2) angular displacements, (3) relative phases. Some movement variables were chosen on the basis of a study which identified some essential kinematic differences between normal walking and racewalking [START_REF] Cairns | A biomechanical analysis of racewalking gait[END_REF].

Global gait parameters.

Four global gait parameters were analyzed: (1) stride frequency (Hz) defined as the inverse of cycle duration, (2) stride length (m) defined as the product of cycle duration and concurrent treadmill velocity, (3) relative duration of thigh's backward swing to complete cycle D (%), (4) sternum vertical displacement STRN (mm) defined as the amplitude of sternum marker's vertical displacement during a cycle reflecting the upper body's vertical displacement. Note that third global variable D resembles the gait duty factor (ratio of stance phase duration to stride duration).

Angular displacements.

An overall of eight body segments were used to study all angular displacements. A segment was defined as the line connecting two strategic positions determined by markers. Figure 1 shows that the thorax and pelvis segments (1 and 2) link right and left shoulders and pelvis' markers, respectively. The forearm segment (3) links the elbow and wrist markers. The arm segment (4) links the shoulder and elbow markers. The trunk segment (5) links the sternum's marker to the midpoint of the pelvis segment. The thigh segment (6) links the markers of the thigh and knee. The shank segment (7) links the knee and ankle markers and the foot segment (8) links the toe and heel markers.

Once body segments were defined, two types of angular displacements were studied. First, a projected angle consisted in the angle between a body segment and the laboratory Y or Z axes, projected in a precise plane. The thorax and pelvis frontal rotations (and ) represented the frontal projection of the angles between these segments and the laboratory Yaxis (Fig. 1a). The transverse rotations of thorax and pelvis ( and ) were determined as the transverse projection of the angles between these segments and the laboratory Y-axis (Fig. 1c). Moreover, the arm and trunk sagittal rotations ( and ) were studied and defined as the sagittal projection of the angles between these segments and the laboratory Z-axis (Fig. 1b). Second, some joint angles were studied and defined as the absolute 3D angle between two segments connected by a common marker or between two non connected segments. The elbow and knee joint angles ( and ) were defined as the angles between two connected segments, namely the arm and forearm segments and the thigh and shank segments. The ankle joint angle () was the angle contained between the non-connected shank and foot segments (Fig. 1b).

For each of the projected angles, minimal (backward or downward), maximum (forward or upward) and amplitude (max-min) values were analyzed. For elbow joint angle, peak flexion, peak extension and amplitude values were assessed. Moreover, three racewalking-related variables were examined: ankle dorsiflexion at heel strike, knee flexion during early stance and the percentage of cycles within a trial in which a hyperextension of the knee was observed at mid-stance (defined in this analysis as greater than 175°, [START_REF] Cairns | A biomechanical analysis of racewalking gait[END_REF]. 

Please insert figure 1 around here

Relative Phases.

The discrete linear relative phase of a key event with respect to a reference cycle was calculated as the ratio between: (1) the time elapsed between the beginning of the reference cycle and the key event, and (2) the duration of the reference cycle. This ratio was multiplied by 360 in order to express the phase in degrees. Several relative phases between different ipsilateral segments and joints angles were studied (see list in Table 1).

Please insert Table 1 around here

Energetic and perceived exertion variables

Oxygen consumption (VO 2 ) and heart rate (HR) data were recorded continuously during learning sessions S1, S4, S6 and S7. For each practice trial, gas exchange data and heart rate were averaged between the third and fourth minute, corresponding to a steady state. The net VO 2 per distance traveled was calculated [(steady state VO 2 -rest VO 2 ) / speed × 60] to obtain the energetic cost of transport (ECT), in ml.kg -1 .km -1 (di Prampero, 1986) with speed expressed in km.h -1 and a rest VO 2 value set at 5 ml.kg -1 .min -1 [START_REF] Medbo | Relative importance of aerobic and anaerobic energy release during short-lasting exhausting bicycle exercise[END_REF].

Ratings of peripheral (PPE) and central perceived exertion (CPE) were collected on the last 20s of the 4 th minute of each trial, by asking the participants to raise the index to indicate a "yes" as the experimenter read up the scale.

2.5.

Statistical analysis

In order to assess the direct effects of the 3 given instructions on the gait pattern, normal walking at PTS (S0, from the transition trials) was compared to the first trial of racewalking (S1) at PTS with a paired t-test for all movement and physiological variables.

Since the higher speed range was used only in the second half of learning sessions, all dependent variables were submitted to two separate analyses of variance, referred to as ANOVA 1 and ANOVA 2. ANOVA 1 was designed with 3 × 3 repeated measures [3 learning sessions (S1, S4, S7) × 3 speeds (PTS, PTS+1, PTS+2)]. ANOVA 2 was performed with 3 × 5 repeated measures [3 learning sessions (S4, S6, S7) × 5 speeds (PTS, PTS+1, PTS+2, PTS+3, PTS+4)]. The significance of p values was adjusted according to the so-called Huynh-Feldt procedure in order to control for possible violations of the assumption of compound symmetry [START_REF] Huynh | Conditions under which mean square ratios in repeated measures designs have exact F-distributions[END_REF]. Analyses were completed by post-hoc Tukey's HSD tests for pairwise comparisons.

In order to examine the relationship between physiological, perceived exertion and kinematic variables, Pearson's product moment correlation coefficient (R) between the values of selective physiological, kinematic and perceived exertion variables in S1 and S4 at moderate speeds (PTS, PTS+1, PTS+2) were calculated.

All tests were realized with Statistica 7.1 package (Statsoft, 2005) with a level of significance set at p < .05.

Results

Although participant #7 had never practiced racewalking, he had a different background than the other participants. As a confirmed endurance-running athlete he presented a higher level in racewalking probably due to the experience gained while training next to high level racewalkers. Therefore, data of participant #7 have been discarded from tables, figures and statistical analyses to ensure the homogeneity of population.

Individual VO 2max and PTS values are represented in Table 2.

Please insert Table 2 around here

Changes in the walking pattern at S1

Paired t-tests were used to compare all movement and physiological variables between normal walking at S0 and racewalking at S1 when locomoting at the preferred transition speed (PTS). The goal was to analyze the immediate effect of the given instructions on the walking pattern. Results are presented in Table 3. Participants spontaneously re-organized the thigh's segmental movement by decreasing the relative duration of its backward motion with respect to a complete cycle. The pelvis downward rotation in frontal plane was significantly increased. Participants also directly accomplished Instruction #3 at S1 by significantly reducing the elbow's peak flexion and extension. However, Instructions #1 and #2 did not bring on significant modifications at the knee and ankle joint angles. Results also showed significant increase in variability at S1 compared to S0 for the pelvis, trunk and elbow angular displacements. This movement reorganization at S1 was not accompanied by any changes in physiological variables (VO 2 , ECT and HR).

Please insert Table 3 around here

Practice-related changes at moderate speeds (ANOVA 1)

ANOVA 1 with 3 (S1, S4, S7) × 3 (PTS, PTS+1, PTS+2) repeated measures was performed on all movement and physiological variables at moderate treadmill velocities. In order to focus exclusively on practice-related changes, only variables that exhibited a significant main effect of practice or a significant interaction between factors (p < .05) are reported (Table 4).

Global variables.

Results showed a significant main effect of practice on all global gait parameters and one global variability (Fig. 2). No significant interaction between factors was revealed. With practice, the relative duration of the thigh's backward swing underwent another significant decrease (after a decrease from S0 to S1) and exhibited less variability. Participants reduced the stance phase to catch up heel strike more rapidly. The significant main effect of practice on the lower limbs re-organization was also revealed by an increased stride frequency and a reduced stride length. A significant decrease in the sternum's vertical displacement (STRN) was also observed, showing a more linear progression of the upper body in space. Moreover, post-hoc analyses showed that the significant changes in global variables occurred between S1 and S4 and not between S4 and S7 pointing out an early re-organization in global gait parameters (Table 4).

Please insert figure 2 around here

Angular displacements.

A main effect of learning was found for three angular displacement variables while no interactions were reported (Fig. 3,Table 4). With practice, participants decreased significantly the thigh's maximal backward rotation in sagittal plane. This quantitative change is in agreement with the qualitative modification found previously (section 3.2) showing an immediate global re-organization in the relative duration of thigh's backward swing. Moreover, less variability was found for the amplitude of trunk's sagittal rotation, accounting for an improved stability in the antero-posterior motion of the upper body. Post-hoc analyses showed that these changes occurred between S1 and S4. Variability of elbow's amplitude decreased with learning and post-hoc revealed a significant difference between S1 and S7 (Table 4).

Please insert figure 3 around here

Relative phases.

Three relative phases were significantly modified throughout practice (Fig. 4, Table 4). Results showed no significant interactions for relative phase variables. The mean relative phase  of maximal foot dorsiflexion in the thigh cycle decreased with learning, whereas the mean relative phase   of the knee maximal flexion in the thigh cycle increased with learning. This reveals a distal re-organization of lower intra-limb coordination. Another re-organization in coordination was shown in the practice-related increase of the mean relative phase   of maximal pelvis frontal upward rotation in the thorax frontal rotation cycle. Post-hoc pairwise comparisons showed that these significant changes occurred between S1 and S4. The variability of   and   decreased significantly from S1 to S4, but not from S4 to S7. Fig. 4 even shows that the variability of   and   tended to increase between S4 and S7 when racewalking at PTS.

Please insert figure 4 around here

Physiological variables and perceived exertion.

A significant main effect of practice was indicated for VO 2 , ECT and PPE, while no interactions were revealed for physiological and perceived exertion variables. Post-hoc showed a significant reduction in these variables between S1 and S7 while no significant differences were pointed out between S1 and S4 (Fig. 5). No significant improvements were revealed for HR and CPE over the learning sessions (Table 4).

Please insert figure 5 around here Please insert Table 4 around here

Correlations.

Since STRN (sternum vertical displacement) was the kinematic variable that presented the highest size effect with practice between S1 and S4 (Table 4), it was chosen to test correlations between changes in movement, physiological and perceived exertion data. Correlations between STRN, VO 2 , ECT, HR, PPE and CPE were tested for values obtained in S1 and S4. Results showed that STRN was significantly correlated with ECT and PPE, the two latter variables being also significantly correlated (Table 5).

Please insert Table 5 around here

3.3.

Late practice effects (S4 -S7) for all tested speeds (ANOVA 2)

ANOVA 2 with 3 (S4, S6, S7) × 5 (PTS, PTS+1, PTS+2, PTS+3, PTS+4) repeated measures was performed on all the movement and physiological variables to test main effects of practice, of speed and their interaction between S4 and S7. Only variables that exhibited either a significant main effect of practice or a significant interaction between speed and practice effects are reported. There were only two such variables (Fig. 6). ANOVA 2 on pelvis max. downward frontal rotation yielded a significant main effect of practice [F(2,10)=5.27, ²= 0.51, p<.05], of speed [F(4, 20)=22.08, ²= 0.82, p<.05] as well as an interaction [F(8, 40)=4.59, ²= 0.48, p<.05]. Post-hoc showed that, for the lowest speeds (PTS, PTS+1), significant improvements occurred between S4-S6 and S4-S7. At PTS+2, significant improvements occurred only at S7. Moreover, ANOVA 2 on elbow max. extension yielded a significant main effect for practice [F(2, 10)=1.19, ²= 0.67 p<.05]. Fig. 6 and posthoc test show that elbow max. extension increased significantly between S4 and S7 at the lowest speed (PTS), after a decrease between S1 and S4 (section 3.3.1). No other variables such as global gait parameters, relative phases, physiological parameters or perceived exertion were modified during the second half of the learning protocol.

Discussion

The first goal of this study was to assess to what extent the fundamental learning strategies presented in the literature of motor learning (i.e. [START_REF] Bernstein | The co-ordination and regulation of movement[END_REF][START_REF] Newell | Coordination, control and skill[END_REF] also apply to the learning of a gross-motor skill like racewalking. The choice of this skill is appropriate since racewalking is an athletic activity that involves complex coordinations between both upper-and lower-body segments and both proximal and distal segments. Furthermore, we expected that the choice of a highly energy-demanding task such as racewalking would help us get insight into the nature of the link between movement refinement and movement economy.

Early reorganization in movement

By observing the immediate adaptations in the gait pattern occurring at the first learning session of racewalking, we meant to draw some conclusions on whether skill acquisition starts proximally (or distally), and how this might be influenced by instructions. The instructions, relative to racewalking specificities and regulation (IAAF, 1995), were focused on three distal joint angles, namely the elbow, the knee and the ankle. Participants immediately achieved the required flexed elbow, by reducing the maximal elbow flexion and extension compared to normal walking. This immediate change in elbow motion was associated with an increase in variability. In contrast, no significant change in amplitude or variability was observed in the lower limb angles, namely knee and ankle. What might differ between the different expected intra-limb coordinations is whether they already belonged or not to the participants' initial gait repertoire. Indeed, the instruction concerning the elbow was presumably easy to accomplish since it resembles the flexed elbow performed in running. Conversely, the instructions concerning the knee (keeping it extended during stance) and the ankle (maximal dorsiflexion at heel strike) could be considered as "artificial" in the sense that these required coordinations did not belong to the participants' initial repertoire and needed therefore to be learnt. Moreover, the elbow joint was not subject to the motorized treadmill constraint unlike the heel and knee joints, for which this additional mechanical constraint had to be surpassed in order to establish the new required pattern.

Another result that needs to be put forward is that the early reorganization observed in the movements of body segments was not directly specified by the instructions (except elbow motion). Indeed, an increase in the amplitude of the pelvis downward rotation in frontal plane was pointed out at S1 compared to normal walking (see Table 3). According to [START_REF] Cairns | A biomechanical analysis of racewalking gait[END_REF], pelvis rotations in frontal plane play a key role in minimizing the vertical excursions of the upper body to compensate for the straightening of the leg. Participants also reduced the relative duration of the thigh's backward swing at S1 compared to S0, showing improvements towards a more adapted stance/suspension sequence approaching skilled racewalkers' duty factor [START_REF] Cairns | A biomechanical analysis of racewalking gait[END_REF]. These two results reveal an early reorganization in movement in order to achieve the task as instructed. Furthermore, increased variability in the pelvis and trunk rotations was also observed at S1 compared to S0, which brings two possible interpretations. First, the larger variability of the upper body movement at S1 compared to S0 could be a compensatory strategy to maintain balance in the face of antero-posterior perturbations created by the effort to hold the knee blocked as instructed and the "drag along" mechanical treadmill effect. Second, the release of the upper body could reveal an exploratory behavior or a search for the most appropriate pattern [START_REF] Ko | Postural coordination patterns as a function of dynamics of the support surface[END_REF]. This could reflect a destabilization of spontaneous tendencies (i.e. walking pattern) to facilitate the adoption of more consistent modes of coordination [START_REF] Newell | Motor skill acquisition[END_REF].

Aside from the elbow instruction considered to be easy to accomplish, it is important to emphasize that the early reorganization in movement and changes in variability did not concern distal lower segments as expected from the given instructions. Changes in movement mainly occurred at the upper body and proximal levels where no specific instruction was given, but also, where the mechanical treadmill constraints did not apply as much as they did on lower distal segments. This could therefore go in line with the idea that complex motor learning (especially for phylogenetic activities such as locomotion) may preferably start at a proximal level. The early establishment of a new relative thigh motion and quantitative changes in movement support the hypothesis of the existence of a first "coordination stage" in motor learning [START_REF] Newell | Coordination, control and skill[END_REF], where the novice first tries to establish basic spatial-temporal relations between the system's components for functional execution of the task.

The early reorganization in movement at S1 did not induce any additional metabolic demands, since no significant differences in VO 2 or ECT were revealed at S1 compared to normal walking (S0). This lack of change could possibly indicate that metabolic aspects were not specifically involved at this early stage of learning. It is important to note, however, that the speed intensity used (i.e. PTS = 7.75 ± 0.77 km.h -1 ) was probably not powerful enough to engender a discriminatory factor in the level of effort produced. Yet, we believe that in this first stage of learning (i.e. coordination stage; [START_REF] Newell | Coordination, control and skill[END_REF] the beginner rather focuses on accomplishing the task demands with no specific reliance on metabolic aspects.

Progression in skill acquisition

The learning sessions brought on relatively large significant modifications in movement variables. Among the variables that were immediately modified at S1 compared to S0, the relative duration of the thigh's backward swing underwent another significant decrease in values with the learning sessions. This variable seemed to play a key role in the realization of the task, where not only its value continued optimizing but also presented less variability with learning. The reorganization of the lower limb relative motion was accompanied by the emergence of new and less variable coordinative patterns (i.e. phase relationships). Between S1 and S4, participants modified the relative phases between foot/thigh and knee/thigh. Interestingly, changes in coordination modes concerned more distal segments in comparison to the immediate proximal adaptations at S1. The reorganization in coordination is broadly consistent with Newell & van Emmerik's proposition (1990) arguing in favor of the existence of a directional trend, from proximal to distal levels.

Moreover, in this study, movement reorganization occurred almost entirely in the first half of the learning sessions, between S1 and S4, for moderate speeds (PTS, PTS+1, PTS+2). These findings could suggest a rapid reach of a higher learning stage at S4 where a coordinative organization is indeed being assembled. According to [START_REF] Newell | Coordination, control and skill[END_REF], the second stage of learning, also called "control stage" is marked by the evolution of topological relations between coordinative patterns (i.e. relative phases), a decrease in dysfunctional variability and a higher consistency in task realization. Evidence of a higher consistency in the performance was given by the gait spatial-temporal characteristics. With practice, participants spontaneously increased stride frequency, a strategy used in skilled racewalking to avoid the loss of ground contact [START_REF] Menier | The relation of oxygen intake and velocity of walking and running, in competition walkers[END_REF]). As a result, participants accomplished one of the main criteria associated with skilled racewalking by reducing the vertical displacement of the upper body, reflecting a better realization of the task. Furthermore, the motions of the elbow and trunk converged by S4 to more reproducible and stable patterns with a significant decrease in variability. In this study, participants weren't expected to reach the "skill stage" of learning since 7 learning sessions were surely insufficient to approach optimal performance [START_REF] Newell | Coordination, control and skill[END_REF].

At moderate speeds, no significant improvements in movement were noted between S4 and S7. However, it seems that the introduction of higher speeds (PTS+3, PTS+4) at S4 had an influence on the frontal pelvis rotation, which is considered to be a key factor in reducing the vertical upper body's displacement while maintaining the leg straightened [START_REF] Cairns | A biomechanical analysis of racewalking gait[END_REF]. The better utilization of the pelvis frontal rotation was observed between S4 and S7, as higher speeds probably constrained the system to adopt a more appropriate mode. What can be hypothesized is that the time scale of the progression in skill acquisition can possibly be reduced by modulating the treadmill speed, constraining somehow the system to find more appropriate movement patterns. Yet, further investigation is needed to confirm this hypothesis.

Metabolic energy expenditure, perceived exertion and movement reorganization

In order to ensure that changes throughout learning sessions were not related to improvements in physiological conditioning, all participants were required to present a good aerobic fitness level (VO 2max : 56.8 ± 7.32 mlO 2 .kg -1 .min -1 ). The intensity (45 -60% VO 2max ) and duration (7 × 30 min) of practice trials were not sufficient to engender changes in aerobic fitness level to the studied population [START_REF] Green | Metabolic adaptations to short-term training are expressed early in submaximal exercise[END_REF].

Results pointed out a continuous decline in energetic cost of transport (ECT), oxygen uptake (VO 2 ) and peripheral perceived exertion (PPE) over the course of learning sessions (Fig. 5). Even though the decrease in metabolic values and PPE became significant only at S7 when compared to S1, a decreasing trend was also visible between S1 and S4. This decreasing trend in metabolic variables and PPE happened concurrently with the process of early movement reorganization (S1-S4). The "control stage" of learning was thereby accompanied by an optimization in metabolic aspects and peripheral perceived exertion. This trend could be associated to the establishment of more economical coordination patterns.

Indeed, significant correlations were shown, from S1 to S4, between ECT and PPE (r = 0.53) and between PPE and the upper body's vertical displacement (STRN) representing the global movement reorganization (r = 0.44), explaining 28% and 19% of the total variance, respectively. In general, studies on perceived exertion scales reported high correlations (r > 0.8) between perceived exertion and physiological responses [START_REF] Hampson | The influence of sensory cues on the perception of exertion during exercise and central regulation of exercise performance[END_REF][START_REF] Faulkner | Overall and peripheral ratings of perceived exertion during a graded exercise test to volitional exhaustion in individuals of high and low fitness[END_REF] while using increments in exercise intensity in the protocol. One main purpose of these studies was indeed to prove the relationship between perceived exertion and physiological responses. However, in the motor learning framework, our results should be related to the work of [START_REF] Sparrow | Effects of practice and preferred rate on perceived exertion, metabolic variables and movement control[END_REF] who studied the effect of learning a rowing ergometer task at a constant power output on perceived exertion, metabolic variables and movement control with inexperienced participants. These authors did not find significant correlations between perceived exertion and metabolic variables despite an associated decrease of these variables, probably due to the insufficiently large changes in metabolic variables with practice. It is important to note that the correlations in this study came out significant although exercise intensities were also moderate (i.e. locomotion speed) and did not engender large variations PPE. At this stage, a clear link between global movement reorganization, metabolic efficiency and sensory information regarding peripheral perceived exertion can be put forward. In line with these results, Murray and collaborators speculated that "the rationale for the unnatural appearing movements of racewalking must lie in the need to diminish the amplitude of the vertical excursion of the mass center of the body in order to conserve mechanical energy" [START_REF] Murray | Kinematic and electromyographic patterns of Olympic race walkers[END_REF].

On the other hand, even though a significant correlation was revealed between the global movement variable, ECT and PPE, it is also clear that movement reorganization (i.e. performance) had essentially reached a plateau at S4 while ECT and PPE continued optimizing till the last session. [START_REF] Almasbakk | The efficient learner[END_REF] have found similar results in a ski simulator learning task. The authors supported [START_REF] Sparrow | The efficiency of skilled performance[END_REF] hypothesis on the theoretical relationship between performance and energy expenditure; i.e. that even after the reach of a plateau in performance, energy expenditure would continue decreasing, probably due to improvements of neuromuscular coordination.

In the search for a potential primary stimulus to movement reorganization, it is important to note that heart rate and central perceived exertion presented no reliable improvements with learning and showed no significant correlation with the global movement reorganization. It seems that metabolic efficiency and perceived exertion related to peripheral variables (PPE) stand as more powerful stimuli than CPE or HR for modifications to coordination and control with learning. Indeed, PPE presented the highest size effect of learning ( 2 = .64), the highest correlation with the global movement variable (STRN) and was therefore clearly more reduced with learning compared to all other physiological parameters and CPE. The perceived exertion is known to involve the integration of multiple afferent signals from peripheral and central variables [START_REF] O'dwyer | Metabolic energy expenditure and accuracy in movement: Relation to levels of muscle and cardiorespiratory activation and the sense of effort[END_REF] and could precisely regulate exercise performance [START_REF] Hampson | The influence of sensory cues on the perception of exertion during exercise and central regulation of exercise performance[END_REF]. In this study, it seems that the afferences from receptors located in the muscles, tendons and joints, might have contributed more largely to the movement reorganization process, for optimized metabolic efficiency, than sensory information concerning cardio-respiratory responses. It has been shown that electromyographic activity of the major group muscles, for upper and lower body, are significantly increased in racewalking compared to normal fast walking [START_REF] Murray | Kinematic and electromyographic patterns of Olympic race walkers[END_REF]. In this view, one could think that sensations resulting from afferent peripheral signals from muscles, tendons and joints receptors might require a decision to adjust the coordination and control of movement patterns, resulting in an increased efficiency. This suggestion is in line with Sparrow et al.'s (1999) conclusions on the important role that peripheral sensation of effort might play in guiding movement pattern reorganization for metabolic optimization with increasing skill. However, the role of peripheral perceived exertion as a primary stimulus to movement reorganization, for metabolic optimization with increasing skill, is clearly worthy of further study.

Conclusion

The present findings support the existence of an early/immediate reorganization in movement with learning, presented in [START_REF] Newell | Coordination, control and skill[END_REF] model as the "coordination stage". Progression in skill marked the reach of the "control stage", evidenced by significant evolution of topological relations between coordinative patterns (i.e. relative phases), a decrease in dysfunctional variability and a higher consistency in task realization, evolving following a directional trend, from proximal to distal levels. An optimization trend of metabolic aspects occurred concurrently with the movement reorganization. Significant correlations confirmed a relationship between global movement reorganization, metabolic energy expenditure and peripheral perceived exertion. More specifically, it seems that peripheral perceived exertion, resulting from afferent signals from receptors in muscles, joints and tendons could be an important factor in refining movement and in minimizing metabolic energy expenditure. This hypothesis needs further investigation to better understand the role of perceived exertion, in guiding movement patterns, when practicing a highly energydemanding and biomechanically constrained motor task.

TABLES

Fig. 1 .

 1 Fig. 1. Representation of studied angular displacements. a: front view; b: side view; c: top view. The circle with a cross represents Y-axis oriented backwards and dotted circles represent X and Z axes oriented towards the reader. 1: thorax segment; 2: pelvis segment; 3: forearm segment; 4: arm segment; 5: trunk segment; 6: thigh segment; 7: shank segment; 8: foot segment. thorax frontal rotation;pelvis frontal rotation thorax transverse rotation; pelvis transverse rotation; arm sagittal rotation; trunk sagittal rotation; elbow joint angle; knee joint angle; ankle joint angle.

Fig. 2 .

 2 Fig. 2. Representative graphs of global gait parameters that demonstrated a main effect of practice (ANOVA 1). Variables are plotted as a function of learning sessions (S1, S4 and S7) for the three moderate speeds (PTS, PTS+1 and PTS+2): (A) stride frequency; (B) stride length; (C) vertical displacement of the sternum; (D) relative duration of thigh backward

Fig. 4 .

 4 Fig. 4. Representative graphs of relative phase variables that demonstrated a main effect of practice (ANOVA 1). Variables are plotted as a function of sessions (S1, S4 and S7) for the three moderate speeds (PTS, PTS+1 and PTS+2): (A) relative phase of maximum foot dorsiflexion in the thigh cycle (B) relative phase of knee maximum flexion in the thigh cycle; (C) relative phase of maximum pelvis upward rotation in the thorax rotation cycle; (D) variability of foot/thigh; (E) variability of knee/thigh. Error bars indicate within participant standard deviation.

Fig. 5 .

 5 Fig. 5. Representative graphs of physiological variables and perceived exertion that demonstrated a main effect of practice (ANOVA 1). Variables are plotted as a function of sessions (S1, S4 and S7) for the three moderate speeds (PTS, PTS+1 and PTS+2): (A) oxygen uptake; (B) energetic cost of transport; (C) peripheral perceived exertion. Error bars indicate within participant standard deviation.

Fig. 6 .

 6 Fig. 6. Representative graphs of variables that demonstrated a main effect of late practice (ANOVA 2). Variables are plotted as a function of sessions (S0, S4, S6 and S7) according to speeds (PTS, PTS+1, PTS+2, PTS+3 and PTS+4): (A) elbow's maximum extension; (B) pelvis maximum downward rotation. Error bars indicate within participant standard deviation.

Table 1

 1 Relative Phases

	Name	Key event	Reference cycle (from max to max)
	 1	max. foot dorsiflexion (sagittal plane)	thigh forward rotation (sagittal plane)
	 2	max. knee flexion during swing (sagittal plane)	thigh forward rotation (sagittal plane)
	 3	max. pelvis upward rotation (frontal plane)	thorax upward rotation (frontal plane)
	 4	max. pelvis forward rotation (transverse plane)	thorax forward rotation (transverse plane)

Table 2

 2 Individual results in preliminary tests: VO 2max and PTS values

	Participants	1	2	3	4	5	6	Mean ± SD
	VO 2max (mlO 2 .kg -1 .min -1 )	58.43	53.02	51.76	53.81	64.76	65.73	57.92 ± 6.11
	PTS (km.h -1 )	7.25	7.75	6.75	7.50	8.38	8.88	7.75 ± 0.77
	PTS: preferred transition speed

Table 3

 3 Variables that exhibited significant differences between S0 and S1 at PTS with a paired t-test (p < .05)

	Sessions	Student's t

Table 4

 4 Variables that exhibited a significant main practice effect at moderate speeds (ANOVA 1)

	Main effect of practice	Post-hoc

Table 5

 5 Pearson's R correlation coefficients between physiological variables (VO 2 , ECT and HR), kinematic variable (STRN) and perceived exertion (PPE and CPE), for S1 and S4 at moderate speeds STR N

			ECT	VO 2	PPE	H	CP
	STRN	1			R	E
	ECT	.36*	1
	VO 2	.11	.91*	1
	PPE	.44*	.53*	.44*	1
	HR	.00	.14	.37*	.30	1
	CPE	.18	.45*	.43*	.81*	.07	1
	* p < .05. N=36

Acknowledgements

The authors are grateful to W.A. Sparrow for his advices and suggestions in the preparation of this research.


M Anwar Hasan

Christophe Negre

Sequential Multiplier with Sub-linear Gate Complexity

Keywords: Binary polynomial multiplication, sequential multiplier, Horner scheme, sub-linear gate complexity

In this article, we present a new sequential multiplier for extended binary finite fields. Like its existing counterparts, the proposed multiplier has a linear complexity in flip-flop or temporary storage requirements, but a sub-linear complexity in gate counts. For the underlying polynomial multiplication, the proposed field multiplier relies on the Horner scheme.

INTRODUCTION

Multiplication over finite fields is used in both symmetric and asymmetric key cryptosystems, and has been a subject of study, especially for its improved implementation, among many researchers as evidenced in their publications, see for example [START_REF] Mastrovito | VLSI Designs for Multiplication over Finite Fields F (2 m )[END_REF], [START_REF] Sunar | Mastrovito Multiplier for All Trinomials[END_REF], [START_REF] Hasan | A Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields[END_REF], [START_REF] Paar | A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields[END_REF], [START_REF] Wang | Bit serial multiplication in finite fields[END_REF], [START_REF] Reyhani-Masoleh | A New Bit-Serial Architecture for Field Multiplication Using Polynomial Bases[END_REF], [START_REF] Guajardo | Efficient Hardware Implementation of Finite Fields with Applications to Cryptography[END_REF]. In this article, we consider a class of hardware architectures for multiplication over extended binary finite field F 2 n . For a small size field like the one used in the well known symmetric key system Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], multiplication can be easily realized with a simple look-up-table (LUT), where the product of each combination of input is pre-stored, preferably in a read-only-memory (ROM). This table based method is however impractical for large size fields used in modern asymmetric key cryptosystems like Elliptic Curve Cryptography (ECC) [START_REF] Miller | Use of elliptic curves in cryptography[END_REF], [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF]. Asymptotically, a look-up table for multiplication can take as much as O(n2 2n ) bits of ROM and the time delay would be essentially equal to the table access time, which is normally a function of the table size. Techniques exist to reduce the table size at the expense of an increased number of table accesses along with logic circuits.

For high speed multiplication over a large field, an alternative approach is to use only logic circuits or gates in some parallel way and to perform a multiplication on-the-fly, e.g., a fully bit parallel multiplier.

For ECC, where the value of n is only a few hundreds, a practical bit-parallel multiplier would take O(n 1+ǫ ) logic gates, where 0 < ǫ ≤ 1, and have a time delay of O(log n) layers of gates.

In constrained environments, where silicon space is of prime concern, a fully bit parallel multiplier for a large field is generally too big to fit the design. On the other end of the spectrum of choices, it is possible, at least in theory, to realize a multiplier with as few as only two gates -one XOR and one ANDwhere the gates will be used repeatedly and many intermediate bit-level results will need to be stored.

We will refer to this type of multipliers as super-sequential, since they would take O(n 1+ǫ ) iterations or clock cycles.The storage requirement for a super-sequential multiplier would be at least O(n 1+ǫ ). Because of large timing and memory requirements, super-sequential multipliers are likely to be least attractive for both constrained and high speed applications and this is perhaps why no practical design of the super-sequential multiplier has been reported in the literature.

Between the above two extremes, namely fully parallel and super-sequential multipliers, one can find various sequential multipliers, either at bit or digit-level. A sequential multiplier operates in an iterative way over a number of clock cycles, typically O(n) cycles for bit sequential or O(n/d) cycles for digit sequential architecture, where d is the digit size. A bit sequential multiplier has a shorter critical path than its digit sequential counterpart. For a bit or digit sequential multiplier, since intermediate results are stored in registers or read-write memories, the storage requirement is at least O(n) bits. Besides registers, a sequential multiplier also requires logic gates, generally in the amount of O(n), i.e., linear to n.

In our work, we differentiate ROM from registers in the usual way. In other words, while the content of a ROM is fixed and specific to a certain arithmetic operation, the content of a register can change.

More importantly, registers are time-shared, i.e., a set of registers can be used by multiple operations, for example, additions, multiplication and inversion, provided that these operations are not executed simultaneously. On the other hand, like ROM but unlike registers, most of the logic gates are assumed to be specific to a certain operation and not shared. As a result, even if an arithmetic unit, such as a multiplier, can be designed to take advantage of time shared registers, there is still a need to reduce the amount of logic gates, especially for area constrained applications.

In this article, we propose a new sequential multiplier. Like its existing counterparts the proposed one requires O(n) bits of registers, but only O(n 1-ǫ ), 0 < ǫ ≤ 1, logic gates. To the best of our knowledge, no sequential multiplier has been reported earlier that has a gate count sub-linear to n. To give an idea about where the proposed multiplier fits with respect to various others, in Table 1 we list their space and time complexities in an asymptotic or general way.

The remainder of this article is organized as follows. In Section 2, we briefly review schemes for a fully bit parallel and a digit-sequential multiplier. In Section 3, we present our sequential multiplier which is based on the Horner method and has a sub-linear gate complexity. Finally, a complexity comparison and concluding remarks are given Section 4.

TABLE 1 List of different types of multipliers and their complexities

Full LUT n2 2n 0 O(n) 1 Fully parallel circuit O(n 1+ε ) 0 O(log(n)) 1
Digit-sequential circuit O(nd) O(n) O(log(d)) n/d Bit-sequential circuit O(n) O(n) O(1) n Proposed O(n 1-ǫ ) O(n) O(log(n)) O(n)

REVIEW OF EXTENDED BINARY FIELD MULTIPLIERS

Field F 2 n can be viewed as the set of binary polynomials in t modulo an irreducible polynomial P (t) of degree n. Let A(t) and B(t) be two elements of F 2 n . The multiplication of these two elements is

C(t) = A(t) × B(t) mod P (t)
, for which we can use the following two steps:

C ′ (t) = A(t) × B(t), (1)
and then reduce C ′ (t) modulo P (t) to get

C(t) = C ′ (t) mod P (t). (2)

Bit parallel architectures

In this type of architectures, all the bits of the product C = AB mod P are generated in parallel. The design of the circuit is based on pure combinatorial logic and does not make any use of storage or flip-flops. Computations are done with no reuse of circuits. The approach we recall here performs the polynomial multiplication (1) and the reduction (2) separately. The reduction modulo P is generally quite simple when P is sparse (i.e., P is a pentanomial or a trinomial) and in this situation the reduction operation can be implemented with O(n) XOR gates and a delay of O(1). Consequently, we will focus here to the polynomial multiplication which is the most costly and the most complicated part of a finite field multiplier.

• Quadratic multiplier. Let C ′ = 2n-2 i=0 c ′ i t i be the product C ′ = A × B
where A and B are degree n -1 3 polynomials in t. The coefficients c ′ i are given in terms of a i and b i as follows

c ′ 0 = a 0 b 0 , c ′ 1 = a 0 b 1 + a 1 b 0 , . . . . . . c ′ n = a 0 b n + a 1 b n-1 + • • • + a n b 0 , c ′ n+1 = a 1 b n + a 2 b n-1 + • • • + a n b 1 , . . . . . . c ′ 2n-3 = a n-2 b n-1 + a n-1 b n-2 , c ′ 2n-2 = a n-1 b n-1 .
The computation of each c i is performed in parallel with AND gates (for the products a ℓ b j ) and a binary tree of XOR gates. The resulting gate complexity of this polynomial multiplier is equal to n 2 AND gates and n(n -1) XOR gates. The critical path of the multiplier is ⌈log 2 (n)⌉D X + D A where D X and D A are delays for a two input XOR and AND gates respectively.

• Subquadratic multiplier [START_REF] Fan | A New Approach to Sub-quadratic Space Complexity Parallel Multipliers for Extended Binary Fields[END_REF]. A second strategy, which was first proposed in [START_REF] Guajardo | Efficient Hardware Implementation of Finite Fields with Applications to Cryptography[END_REF], is based on the method of Karatsuba. Specifically, the multiplication is performed by applying the following formula recursively

Splitting: A = A 0 + A 1 t n/2 and B = B 0 + B 1 t n/2 ,
Recursive products:

M 0 = A 0 B 0 , M 1 = (A 0 + A 1 ) × (B 0 + B 0 ) and M 2 = A 1 B 1 , Reconstruction: C ′ = M 0 + t n/2 (M 1 + M 0 + M 2 ) + t n M 2 ,
As stated in [START_REF] Guajardo | Efficient Hardware Implementation of Finite Fields with Applications to Cryptography[END_REF], this approach requires 6n log 2 (3) + 8n -2 XOR gates, n log 2 (3) AND gates and has a delay of 3 log 2 (n)D X + D A . Recently, some optimizations have been proposed: Leone in [START_REF] Leone | A New Low Complexity Parallel Multiplier for a Class of Finite Fields[END_REF] has noticed that it is possible to slightly reduce the space complexity of the Karatsuba multiplier if we stop the recursion when we reach polynomials of degree 4 or 8 and then apply quadratic method.

More recently, Fan et al. in [START_REF] Fan | Overlap-free karatsuba-ofman polynomial multiplication algorithms[END_REF] have proposed to use an odd/even splitting which reduces the delay

to 2 log 2 (n)D X + D A .
In Table 2, we recall the complexity of the schoolbook method and then give the complexity of multipliers based on the Karatsuba combined with the optimization approaches of Leone [START_REF] Leone | A New Low Complexity Parallel Multiplier for a Class of Finite Fields[END_REF] and Fan et al. [START_REF] Fan | Overlap-free karatsuba-ofman polynomial multiplication algorithms[END_REF].

Digit Sequential Multiplier

In sequential multipliers, computations are done with reuse of circuits and the final result is obtained over several clock cycles. Here, we review the digit sequential version of the multiplier of Song and Parhi [START_REF] Song | Low-Energy Digit-Serial/Parallel Finite Field Multipliers[END_REF].

Song and Parhi fix a digit size d and define m = ⌈ n d ⌉ and then they rewrite the two polynomials A and

B as follows

A(t) = m-1 i=0 A i (t)t di with deg t A i (t) < d, B(t) = m-1 i=0 B i (t)t di with deg t B i (t) < d.
The left-to-right (L-to-R) method for digit-serial multiplication is based on the following expansion of the product A × B mod P

C = A × B mod P = ((. . . ((AB m-1 mod P )t d + AB m-2 mod P )t d + • • • )t d + AB 1 mod P )t d + AB 0 mod P.
The previous expression results in the following L-to-R multiplication algorithm. It consists of a sequence of multiplications by t d followed by the accumulation of AB i in C modulo P .

Algorithm 1 Left-to-right digit sequential multiplication [12]

Require:

A(t) = m-1 i=0 A i (t)t di and B(t) = m-1 i=0 B i (t)t di . Ensure: C = A × B C ← 0 for i = m -1 to 0 do C ← (t d × C + B i A) mod P end for

Return(C)

In Algorithm 1, the multiplication by t d is performed by shifting the coefficients of C. The multiplication B i × A is done using m parallel quadratic space complexity polynomial multipliers of size d. These digit multipliers compute the product B i A j for j = 0, . . . , m -1. Each product B i A j has degree 2d -2: thus the upper part of this product is added to C j+1 and the lower part to C j . Then the updated value of C has m + 1 digits, since in C m we store the upper part of the product B i A m-1 . If we assume that P = t md + m-1 i=0 P i (t)t id , then we reduce C m modulo P using the following expression

C m t md = m-1 i=0 P i C m t id .
In practical applications, P can be taken as a pentanomial or a trinomial, so the P i 's are in general either equal to zero or sparse. Here, for the sake of simplicity, we will further assume that the only non-zero P i is P 0 . This means that the reduction step consists of C m t md = P 0 C m and can be performed with at most 3(d -1) XOR gates (indeed, if P is a pentanomial, then P 0 has 4 non-zero coefficients).

The resulting digit sequential multiplier is depicted in Fig. 1. The Digit Mult. boxes represent the quadratic parallel polynomial multipliers for degree d polynomials. The complexity of this digit sequential multiplier is given below. Note that S ⊕ represents the number of XOR gates, S ⊗ represents the number of AND gates and D represents the delay of the critical path of the architecture. We remark that the total computational delay is the number of clock cycles times the clock period, whose duration is at least the critical path delay.

S ⊕ = m(d 2 + d -1) + 5d -4, S ⊗ = md 2 , D = ⌈log 2 (d) + 5⌉D X + D A , #Flip-flops = 3md, # Clock cycles = m.
Remark 1: We have restricted our study to a quite specific P but in general when P has degree n and is a pentanomial, a similar approach can be applied with no additional significant complexity. Our choice was motivated only by the simplicity of this special case in the digit sequential design.

SUB-LINEAR GATE COMPLEXITY USING HORNER'S METHOD

In this section, we present a multiplier with sub-linear gate complexity based on the Horner method. Our approach takes advantage of a subquadratic multiplier as well as a digit sequential multiplier. As before, let A(t) and B(t) be two polynomials of degree < n. Let m and d be two integers such that m × d = n.

We rewrite A and B in a digit form as follows:

A(t) = m-1 i=0 A i (t)t di with deg t A i (t) < d B(t) = m-1 i=0 B i (t)t di with deg t B i (t) < d
We multiply A and B using Horner's method. Here we assume that the irreducible polynomial P has the form P = X dm +P 0 where P 0 has a degree less than d and has at most four non-zero coefficients. This assumption is not restrictive, a similar multiplier with the same order of area and delay complexity can be designed with a more general pentanomial P . The resulting method is described in Algorithm 2 and uses the Left-to-Right approach. We have exhibited all the m 2 digit multiplications and we have separated

the operations C + A j B i t jd , 0 ≤ j < m -1 and 0 ≤ i < m, from the operations t d (C + A m-1 B i t d(m-1) ) mod P and (C + A m-1 B i t d(m-1)
) mod P which involve reduction modulo P .

The architecture based on Algorithm 2 is shown in Fig. 2. In this architecture, elements A and B are each stored in a register of m cells, each cell containing d bits. The product C is also stored in a register of m cells and is initialized with m zeros. Registers containing A and C are shifted cyclically once in every clock cycle. On the other hand, B is shifted once after every m clock cycles. At each clock cycle one of the following cases is performed and in Fig. 2 these three cases are indicated in red, blue and green.:

• Case 1 (Red). A digit A j for 0 ≤ j < m-1 is output from the A register and the digit B i is output from B. The A and C registers are left shifted but no shift is operated in the B register. The two digits A j and B i are multiplied in the digit multiplier. Then the data follows the blue lines. This corresponds to the addition of A j B i to C j and the result moves in the right most cell of the C register. The "carry" of A j B i is added to C j+1 and the result is stored in the left most cell of C.

• Case 2 (Blue). The digit A m-1 and B i are output from A and B respectively. The A register is left shifted and the B register is right shifted, but no left shifts are applied to the C register. The two digits A m-1 and B i are multiplied and then, the data follows the red paths. The operation corresponds to the multiplication by t d and the computation of ((C m-1 + A m-1 B i )t md mod P ).

• Case 3 (Green). This is the last step before the output of the product C. At this step, the C register is left shifted. The digits A m-1 and B 0 are output from the A and B registers and then multiplied through the digit multiplier. Then the lower part of the product is added to C m-1 and the upper part is reduced modulo P , i.e., is multiplied by P 0 and added to C 0 and C 1 . and XOR gates and the critical path of the architecture in terms of m and d. For the sake of simplicity, we assume that each path in Fig. 2 is of width d.

• 3m cells of d bits each for A, B and C. Thus, the architecture in Fig. 2 requires 3md flip flops in total.

• The number of AND gates is equal to S ⊗ (d) which is the number of AND gates of the digit multiplier.

The number of XOR gates is equal to S ⊕ (d)+5d, where we have counted the following: the XOR gates of one multiplier of size d, five adders of size d, and 2 × 2d + 2 × d XORs for the two multiplications by P 0 .

• The architecture in Fig. 2 also requires one 1:2 and three 1:3 demultiplexers, and one 2:1 multiplexer where each input/output is d bits wide.

• The critical path delay is equal to D(d) + 4D X + D A where D(d) is the delay of the digit multiplier.

The number of clock cycles is equal to m 2 .

Using the subquadratic complexity results based on [START_REF] Fan | Overlap-free karatsuba-ofman polynomial multiplication algorithms[END_REF] and [START_REF] Leone | A New Low Complexity Parallel Multiplier for a Class of Finite Fields[END_REF] as given in Table 2, we obtain the

COMPLEXITY COMPARISON AND CONCLUSION

We finally obtain a sub-linear gate complexity by fixing the value of d and m as d = √ n and m = √ n. The resulting complexity is given in Table 3. In the same table, we recall the complexity of the digit sequential multiplier of Song and Parhi [START_REF] Song | Low-Energy Digit-Serial/Parallel Finite Field Multipliers[END_REF] reviewed earlier in Section 2 (for which we assume that m = n/d). The results in Table 3 suggest that the proposed sequential multiplier has a gate count which is much smaller than that of the multiplier of [START_REF] Song | Low-Energy Digit-Serial/Parallel Finite Field Multipliers[END_REF]. On the other hand, the proposed multiplier has a longer critical path resulting in a much larger overall delay. Thus the proposed sub-linear gate complexity multiplier offers a new area-time trade-off. For example, if we consider n = 256 (i.e, d = m = 16), the multiplier of [START_REF] Song | Low-Energy Digit-Serial/Parallel Finite Field Multipliers[END_REF] would require 8596 XORs, 8192 ANDs, 16 clock cycles with 9 levels of gates on the critical path, whereas the corresponding values of the proposed multiplier are 397 XORs, 143 ANDs, 256 clock cycles and 11 levels of gates.

Architecture # Logic gates

  or ROM cells # Flip-flops in registers Critical Path Delay # Clock Cycles

Fig. 1 .

 1 Fig.1. Left-to-right digit sequential multiplier of[START_REF] Song | Low-Energy Digit-Serial/Parallel Finite Field Multipliers[END_REF]

Fig. 2 .

 2 Fig. 2. Sub-linear sequential multiplier based on the Horner method

TABLE 2

 2 Complexity of bit parallel binary polynomial multiplier architectures

	Method	Space Complexity	Delay
		# XOR	# AND
	Quadratic	n 2 -1	n 2	DA + ⌈log 2 (n)⌉DX
	Subquadratic [3]	6n log 2 (3) -8n + 2	n log 2 (3)	DA + (2 log 2 (n))DX
	Subquadratic [3] and [7] combined 13 3 n log 2 (3) -8n + 2 16 9 n log 2 (3) DA + (2 log 2 (n) -2)DX

TABLE 3

 3 Comparison with the proposed sequential multiplier(n) + 4)D X + D A n n((log 2 (n) + 2)D X + D A )

	Architecture	# AND	# XOR	#FFs	Critical	# Clock	Overall delay
	Path Delay ⌈log 2 (d) + 5⌉D X + D A (log 2 Song and Parhi [12] Proposed 1.77n 0.78 4.33n 0.78 + 3 √ n + 2 3n nd n(d + 1 -1 d ) + 5d -4 3n	cycles d n	n(⌈log 2 (d)+5⌉D

X +D A ) d

June 26, 2012 DRAFT

To avoid any confusion between Case 2 and Case 3, in Fig. 2 we have used two Mult. by P 0 boxes which perform a multiplication by P 0 in the two distinct paths.

The main differences between Algorithm 1 and Algorithm 2 and their respective architectures are the following:

1) in Algorithm 2 and in the corresponding architecture in Fig. 2, the digit multiplications are done in sequence and not through m parallel digit multipliers.

2) In the proposed multiplier, the digit multiplication uses a subquadratic multiplier, and the digit size d in Fig. 2 is generally larger than the one in Fig. 1.

In Fig. 3, we illustrate the functioning of the proposed multiplier by presenting the first four cycles of the sequential multiplier for n = 32.

Complexity evaluation. Below we list, along with a brief explanation, the number of flip-flops, AND gates Fig. 3. First four steps of the multiplication of A = (t + 1) + (t + 1) × t 24 and B = t + t 7 × t 24 modulo P = t 4×8 + t 7 + t 6 + t + 1 with m = 4 and d = 32 (note that after the demultiplexer, the followed paths are indicated with bold lines)

Digit Mult. Mult. by P0 0 following complexity for the multiplier in Fig. 2 #XOR = 13 (3)