text: x x 1 2 u x 1 c k (cid:15) Figure 8: Dissipative mechanical system. 150 x d x 100 50 a) 0 200 x d x 0 b) −200 0 50 100 t Figure 9: Reference trajectory x for the dissipative mechanical system and trajectory x with d nearby initial condition for u = u (t). ﬀ (cid:0) (cid:1) T trajectory x with initial condition x (0, 0) = 50 0 has a maximal average inter-jump time d (cid:0) (cid:1) d τ > 0. In addition, x (t, j) does not arrive at the origin. To show that the tracking problem is d d not trivial, in the same ﬁgure, a trajectory of (18) is depicted with the same forcing and initial T condition x (0, 0) = 51 0 . Clearly, both trajectories diverge. d For this example, we derive an explicit expression for the distance function. As the reference trajectory x stays away from the origin, we can model the system with D = {0} × (−∞, −r], d with r > 0 suﬃciently small, such that G(D) = {0} × [εr, ∞). Then, (3) yields (cid:13)(cid:18) (cid:19)(cid:13) (cid:13)(cid:18) (cid:19)(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) d(cid:13)(x, y) = m(cid:13)in(d0(x, y), d1(x, y), d2(x, y)), (cid:13) (cid:13) (32) (cid:13) (cid:13) (cid:13) (cid:13) x − z x − z with d (x, y) = inf x , d (x, y) = inf x and d (x, y) = 0 zx=zy∈C y − z 1 zx=G(zy),zy∈D y − z 2 y y d (y, x). We will now ﬁnd explicit expressions for d and d . By the observation that d2(x, y) = 1 0 1 0 inf (cid:107)x−z (cid:107)2+(cid:107)y−z (cid:107)2, we observe that the inﬁmum is attained z = x+y, which is contained zx∈C x x x 2 in C when, ﬁrstly, d (x, y) is suﬃciently small and secondly, x = x with the reference trajectory 0 d suﬃciently far from the origin. Hence, we obtain 1 d (x, y) = √ (cid:107)x − y(cid:107). (33) 0 2 (cid:13)(cid:18) (cid:19)(cid:13) Now, we compute d (x, y) using that (cid:13) (cid:13) 1 (cid:13) (cid:13) (cid:13) (cid:13) 2 x − z d (x, y)2 = inf x (34) 1 y − z zx=G(zy),zy∈D y = inf x2 + y2 + (x + εz )2 + (y − z )2. 1 1 2 y2 2 y2 zy2≤−r 18 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: x

text: x

text: u

text: x

text: c

text: k

text: Figure

text: Dissipative

text: mechanical

text: system.

text: x

text: d

text: x

text: a)

text: x

text: d

text: x

text: b)

text: t

text: Figure

text: Reference

text: trajectory

text: x

text: for

text: the

text: dissipative

text: mechanical

text: system

text: and

text: trajectory

text: x

text: with

text: d

text: nearby

text: initial

text: condition

text: for

text: u

text: u

text: (t).

text: ﬀ

text: T

text: trajectory

text: x

text: with

text: initial

text: condition

text: x

text: has

text: a

text: maximal

text: average

text: inter-jump

text: time

text: d

text: d

text: τ

text: In

text: addition,

text: x

text: (t,

text: j)

text: does

text: not

text: arrive

text: at

text: the

text: origin.

text: To

text: show

text: that

text: the

text: tracking

text: problem

text: is

text: d

text: d

text: not

text: trivial,

text: in

text: the

text: same

text: ﬁgure,

text: a

text: trajectory

text: of

text: is

text: depicted

text: with

text: the

text: same

text: forcing

text: and

text: initial

text: T

text: condition

text: x

text: Clearly,

text: both

text: trajectories

text: diverge.

text: d

text: For

text: this

text: example,

text: we

text: derive

text: an

text: explicit

text: expression

text: for

text: the

text: distance

text: function.

text: As

text: the

text: reference

text: trajectory

text: x

text: stays

text: away

text: from

text: the

text: origin,

text: we

text: can

text: model

text: the

text: system

text: with

text: D

text: −r],

text: d

text: with

text: r

text: suﬃciently

text: small,

text: such

text: that

text: G(D)

text: [εr,

text: Then,

text: yields

text: y)

text: y),

text: y),

text: y)),

text: x

text: z

text: x

text: z

text: with

text: d

text: (x,

text: y)

text: inf

text: x

text: d

text: (x,

text: y)

text: inf

text: x

text: and

text: d

text: (x,

text: y)

text: zx=zy∈C

text: y

text: z

text: zx=G(zy),zy∈D

text: y

text: z

text: y

text: y

text: d

text: (y,

text: x).

text: We

text: will

text: now

text: ﬁnd

text: explicit

text: expressions

text: for

text: d

text: and

text: d

text: By

text: the

text: observation

text: that

text: y)

text: inf

text: we

text: observe

text: that

text: the

text: inﬁmum

text: is

text: attained

text: z

text: x+y,

text: which

text: is

text: contained

text: zx∈C

text: x

text: x

text: x

text: in

text: C

text: when,

text: ﬁrstly,

text: d

text: (x,

text: y)

text: is

text: suﬃciently

text: small

text: and

text: secondly,

text: x

text: x

text: with

text: the

text: reference

text: trajectory

text: d

text: suﬃciently

text: far

text: from

text: the

text: origin.

text: Hence,

text: we

text: obtain

text: d

text: (x,

text: y)

text: Now,

text: we

text: compute

text: d

text: (x,

text: y)

text: using

text: that

text: x

text: z

text: d

text: (x,

text: inf

text: x

text: y

text: z

text: zx=G(zy),zy∈D

text: y

text: inf

text: (x

text: εz

text: (y

text: z

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: for a class of hybrid systems. The proposed design for the distance function takes the nature of the jumps of the hybrid system into account, such that the distance function provides a good comparison between the traject- ories of two solutions, without the “peaking behaviour” along solutions that is expected in the Euclidean distance. The stability properties of trajectories were studied in terms of this distance function. Suﬃcient conditions for stability have been formulated using Lyapunov functions with sub-level sets that consist of disconnected pieces. Moreover, the conditions are formulated in terms of maximum or minimum average inter-jump time conditions to allow for increase of the Lyapunov function over ﬂow or jumps, respectively. In case the jump map is an aﬃne function and the jump set a hyperplane, a piecewise quadratic Lyapunov function was proposed that can be constructed systematically. Focussing on a class of tracking problems for hybrid systems where control is only possible during ﬂow, we designed a switching tracking control law. The asymptotic stability of a reference traject- ory of the closed-loop system can be assessed with matrix conditions obtained from our general theory. Finally, we applied the proposed tracking control law in two examples and observed that the con- trol law achieves accurate tracking. These examples also illustrated that the presented asymptotic stability notion does correspond to desired tracking behaviour. This underlines that the proposed distance function enables a good comparison between hybrid trajectories and has the potential to play an important role in tracking control, observer design and synchronisation problems for hybrid systems. Acknowledgement J.J.B. Biemond is a FWO Pegasus Marie Curie Fellow. This research is supported in part by the European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement no. 257462 HYCON2 Network of excellence. References [1] D. Angeli. A Lyapunov approach to incremental stability properties. IEEE Transactions on Automatic Control, 47(3):410–421, 2002. [2] J.-P. Aubin and H. Frankowska. Set-Valued Analysis. Modern Birkh¨auser Classics. Birkh¨auser, Boston, 2009. [3] J. J. B. Biemond, N. van de Wouw, W. P. M. H. Heemels, and H. Nijmeijer. Tracking control for hybrid systems with state-triggered jumps. IEEE Transactions on Automatic Control, 58(4):876–890, 2013. [4] B. Brogliato. Nonsmooth Mechanics. Springer-Verlag, London, 1999. [5] M. Broucke and A. Arapostathis. Continuous selections of trajectories of hybrid systems. Systems Control Letters, 47:149–157, 2002. [6] F. Forni, A. R. Teel, and L. Zaccarian. Follow the bouncing ball: global results on tracking and state estimation with impacts. submitted to IEEE Transactions Automatic Control, 2011. [7] F. Forni, A. R. Teel, and L. Zaccarian. Tracking control in billiards using mirrors without smoke, Part I: Lyapunov-based local tracking in polyhedral regions. In Proceedings of the 50th IEEE Conference on Decision and Control, Orlando, pages 3283–3288, 2011. [8] F. Forni, A. R. Teel, and L. Zaccarian. Tracking control in billiards using mirrors without smoke, Part II: additional Lyapunov-based local and global results. In Proceedings of the 50th IEEE Conference on Decision and Control, Orlando, pages 3289–3294, 2011. [9] S. Galeani, L. Menini, and A. Potini. Robust trajectory tracking for a class of hybrid systems: an internal model principle approach. IEEE Transactions on Automatic Control, 57(2):344– 359, 2012. 21

text: for

label: paragraph

text: a

text: class

text: of

text: hybrid

text: systems.

text: The

text: proposed

text: design

text: for

text: the

text: distance

text: function

text: takes

text: the

text: nature

text: of

text: the

text: jumps

text: of

text: the

text: hybrid

text: system

text: into

text: account,

text: such

text: that

text: the

text: distance

text: function

text: provides

text: a

text: good

text: comparison

text: between

text: the

text: traject-

text: ories

text: of

text: two

text: solutions,

text: without

text: the

text: “peaking

text: behaviour”

text: along

text: solutions

text: that

text: is

text: expected

text: in

text: the

text: Euclidean

text: distance.

text: The

text: stability

text: properties

text: of

text: trajectories

text: were

text: studied

text: in

text: terms

text: of

text: this

text: distance

text: function.

text: Suﬃcient

text: conditions

text: for

text: stability

text: have

text: been

text: formulated

text: using

text: Lyapunov

text: functions

text: with

text: sub-level

text: sets

text: that

text: consist

text: of

text: disconnected

text: pieces.

text: Moreover,

text: the

text: conditions

text: are

text: formulated

text: in

text: terms

text: of

text: maximum

text: or

text: minimum

text: average

text: inter-jump

text: time

text: conditions

text: to

text: allow

text: for

text: increase

text: of

text: the

text: Lyapunov

text: function

text: over

text: ﬂow

text: or

text: jumps,

text: respectively.

text: In

text: case

text: the

text: jump

text: map

text: is

text: an

text: aﬃne

text: function

text: and

text: the

text: jump

text: set

text: a

text: hyperplane,

text: a

text: piecewise

text: quadratic

text: Lyapunov

text: function

text: was

text: proposed

text: that

text: can

text: be

text: constructed

text: systematically.

text: Focussing

text: on

text: a

text: class

text: of

text: tracking

text: problems

text: for

text: hybrid

text: systems

text: where

text: control

text: is

text: only

text: possible

text: during

text: ﬂow,

text: we

text: designed

text: a

text: switching

text: tracking

text: control

text: law.

text: The

text: asymptotic

text: stability

text: of

text: a

text: reference

text: traject-

text: ory

text: of

text: the

text: closed-loop

text: system

text: can

text: be

text: assessed

text: with

text: matrix

text: conditions

text: obtained

text: from

text: our

text: general

text: theory.

text: Finally,

text: we

text: applied

text: the

text: proposed

text: tracking

text: control

text: law

text: in

text: two

text: examples

text: and

text: observed

text: that

text: the

text: con-

text: trol

text: law

text: achieves

text: accurate

text: tracking.

text: These

text: examples

text: also

text: illustrated

text: that

text: the

text: presented

text: asymptotic

text: stability

text: notion

text: does

text: correspond

text: to

text: desired

text: tracking

text: behaviour.

text: This

text: underlines

text: that

text: the

text: proposed

text: distance

text: function

text: enables

text: a

text: good

text: comparison

text: between

text: hybrid

text: trajectories

text: and

text: has

text: the

text: potential

text: to

text: play

text: an

text: important

text: role

text: in

text: tracking

text: control,

text: observer

text: design

text: and

text: synchronisation

text: problems

text: for

text: hybrid

text: systems.

text: Acknowledgement

text: J.J.B.

text: Biemond

text: is

text: a

text: FWO

text: Pegasus

text: Marie

text: Curie

text: Fellow.

text: This

text: research

text: is

text: supported

text: in

text: part

text: by

text: the

text: European

text: Union

text: Seventh

text: Framework

text: Programme

text: under

text: grant

text: agreement

text: no.

text: Network

text: of

text: excellence.

text: References

text: D.

text: Angeli.

text: A

text: Lyapunov

text: approach

text: to

text: incremental

text: stability

text: properties.

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,

text: J.-P.

text: Aubin

text: and

text: H.

text: Frankowska.

text: Set-Valued

text: Analysis.

text: Modern

text: Birkh¨auser

text: Classics.

text: Birkh¨auser,

text: Boston,

text: J.

text: J.

text: B.

text: Biemond,

text: N.

text: van

text: de

text: Wouw,

text: W.

text: P.

text: M.

text: H.

text: Heemels,

text: and

text: H.

text: Nijmeijer.

text: Tracking

text: control

text: for

text: hybrid

text: systems

text: with

text: state-triggered

text: jumps.

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,

text: B.

text: Brogliato.

text: Nonsmooth

text: Mechanics.

text: Springer-Verlag,

text: London,

text: M.

text: Broucke

text: and

text: A.

text: Arapostathis.

text: Continuous

text: selections

text: of

text: trajectories

text: of

text: hybrid

text: systems.

text: Systems

text: Control

text: Letters,

text: F.

text: Forni,

text: A.

text: R.

text: Teel,

text: and

text: L.

text: Zaccarian.

text: Follow

text: the

text: bouncing

text: ball:

text: global

text: results

text: on

text: tracking

text: and

text: state

text: estimation

text: with

text: impacts.

text: submitted

text: to

text: IEEE

text: Transactions

text: Automatic

text: Control,

text: F.

text: Forni,

text: A.

text: R.

text: Teel,

text: and

text: L.

text: Zaccarian.

text: Tracking

text: control

text: in

text: billiards

text: using

text: mirrors

text: without

text: smoke,

text: Part

text: I:

text: Lyapunov-based

text: local

text: tracking

text: in

text: polyhedral

text: regions.

text: In

text: Proceedings

text: of

text: the

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control,

text: Orlando,

text: pages

text: F.

text: Forni,

text: A.

text: R.

text: Teel,

text: and

text: L.

text: Zaccarian.

text: Tracking

text: control

text: in

text: billiards

text: using

text: mirrors

text: without

text: smoke,

text: Part

text: II:

text: additional

text: Lyapunov-based

text: local

text: and

text: global

text: results.

text: In

text: Proceedings

text: of

text: the

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control,

text: Orlando,

text: pages

text: S.

text: Galeani,

text: L.

text: Menini,

text: and

text: A.

text: Potini.

text: Robust

text: trajectory

text: tracking

text: for

text: a

text: class

text: of

text: hybrid

text: systems:

text: an

text: internal

text: model

text: principle

text: approach.

text: IEEE

text: Transactions

text: on

text: Automatic

text: Control,


text: b) For a jump (x, y) → (x, G(y)) with (x, y) ∈ S , we observe V (x, G(y)) ≤ (cid:107)x − G(y)(cid:107)2 = (cid:107)x − G¯(y)(cid:107)2 , as y ∈ D. Hence, (23) implies (114) in this case.2 P0 P0 c) For a jump (x, y) → (x, G(y)), with (x, y) ∈ S , (14) directly follows from combining a) with 0 the symmetry relation V (x, y) = V (y, x). d) For a jump (x, y) → (G(x), y) with (x, y) ∈ S , symmetry of V and b) imply (14). 2 Hence, we have proven that (14) holds over all feasible jumps, therewith concluding the proof of the lemma. Proof of Theorem 5. We prove this theorem by application of Theorem 2. Lemma 4 proves that (cid:12) (13) and (14) hold for some v > 0. Hence, we now show that the assumptions i(cid:12)n the theorem L (cid:12) prove that (15) is satisﬁed in the sub-level set V = V −1([0, v ]). (cid:0) (cid:1) L L According to Lemma 4, V is diﬀerentiable in V , such that we evaluate (cid:104) ∂V , f(cid:105) for f ∈ L ∂q q F (t, x¯ (t, j), y) only when q = x¯ (t, j)T yT T ∈ V ∩ C , where, for almost all t, F is single- e d d L e e (cid:0) (cid:1) valued, and we distinguish the three cases given by the minimisers of (20). If (x¯ (t, j), y) ∈ S ∩V , d 0 L then ∂V (cid:18) = 2(x¯ (t, j) − y)T P I −I (cid:19) d 0 n n ∂q and Ax¯ (t, j) + E + Bu (t) F = d ﬀ , e Ay + E + B(u (t) − c (x¯ (t, j) − y)) ﬀ 0 d such that (15) is guaranteed by (27). (cid:0) (cid:1) If (x¯ (t, j), y) ∈ S ∩V , then 3) of Lemma 3 implies G¯(y) = (L+MJ)y+H +MK. Consequently d 1 L ∂V = 2(cid:32)sT P I −(L + MJ) (cid:33) ∂q 1 s n and Ax¯ (t, j) + E + Bu (t) d ﬀ Fe(t, x¯d(t, j), y)= Ay+E+B(u (t)− β2Tβ1(t) −c s ) ﬀ β2Tβ2 1 1 with s = x¯ (t, j)−G¯(y) holds. Hence, we obtain ∂V F (t, x, y) = 2sT P (Ax¯ (t, j)+E +Bu (t)− 1 d ∂q e 1 s d ﬀ (L + MJ)Ay − (L + MJ)E − (L + MJ)Bu − β2β2T β (t) − (L + MJ)Bc s . With (26), we ﬁnd ﬀ(t) β2Tβ2 1 1 1 β2β2T β (t) = β (t), such that β2Tβ2 1 1 ∂V F (t, x¯ (t, j), y) = ∂q e d 2sT P (Ax¯ (t, j) + (I − L − MJ)(E + Bu (t)) 1 s d ﬀ − (L + MJ)Ay − β (t) + β c s ). (49) 1 2 1 1 Since y = (L+MJ)−1(−s +x¯ (t, j)−H −MK) = −(L+MJ)−1s +G¯◦(x¯ (t, j)), (which holds 1 d 1 d as max(0, z x¯ (t, j) + z ) = 0 follows from (x¯ (t, j), y) ∈ S ∩ V , cf. Lemma 3) we obtain 1 d 2 d 1 L ∂V F (t, x¯ (t, j), y) = ∂q e d 2sT P ((L + MJ)A(L + MJ)−1 + β c )s , (50) 1 s 2 1 1 where we used the design of β . Hence, (28) guarantees that (15) holds in this case. 1 Now, we focus on the case (x¯ (t, j), y) ∈ S ∩ V . In that case, from 3) of Lemma 3, we observe d 2 (cid:0) L (cid:1) that max(0, z y + z ) = 0 follows from (x¯ (t, j), y) ∈ S ∩ V , cf. Lemma 3. Hence, 1 2 d 2 L ∂V = 2sT P (L + MJ) −I ∂q 2 s n ≤ − (cid:107) − (cid:107) ≤ 2 Agai∈n, when before the jump, V (x,y) e λdvL holds, we conclude that x G(y) 2P0 vL, such that (x,G(y)) S0, as shown in Fig. 5, follows. 27 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: b)

label: list

text: For

text: a

text: jump

text: (x,

text: y)

text: (x,

text: G(y))

text: with

text: (x,

text: y)

text: S

text: we

text: observe

text: V

text: (x,

text: G(y))

text: as

text: y

text: D.

text: Hence,

text: implies

text: in

text: this

text: c)

text: For

text: a

text: jump

text: (x,

text: y)

text: (x,

text: G(y)),

text: with

text: (x,

text: y)

text: S

text: directly

text: follows

text: from

text: combining

text: a)

text: with

text: the

text: symmetry

text: relation

text: V

text: (x,

text: y)

text: V

text: (y,

text: x).

text: d)

text: For

text: a

text: jump

text: (x,

text: y)

text: (G(x),

text: y)

text: with

text: (x,

text: y)

text: S

text: symmetry

text: of

text: V

text: and

text: b)

text: imply

text: Hence,

text: we

text: have

text: proven

text: that

text: holds

text: over

text: all

text: feasible

text: jumps,

text: therewith

text: concluding

text: the

text: proof

text: of

text: the

text: lemma.

text: Proof

text: of

text: Theorem

text: We

text: prove

text: this

text: theorem

text: by

text: application

text: of

text: Theorem

text: Lemma

text: proves

text: that

text: and

text: hold

text: for

text: some

text: v

text: Hence,

text: we

text: now

text: show

text: that

text: the

text: assumptions

text: the

text: theorem

text: L

text: prove

text: that

text: is

text: satisﬁed

text: in

text: the

text: sub-level

text: set

text: V

text: V

text: v

text: L

text: L

text: According

text: to

text: Lemma

text: V

text: is

text: diﬀerentiable

text: in

text: V

text: such

text: that

text: we

text: evaluate

text: ∂V

text: for

text: f

text: L

text: ∂q

text: q

text: F

text: (t,

text: x¯

text: (t,

text: j),

text: y)

text: only

text: when

text: q

text: x¯

text: (t,

text: j)T

text: yT

text: T

text: V

text: C

text: where,

text: for

text: almost

text: all

text: t,

text: F

text: is

text: single-

text: e

text: d

text: d

text: L

text: e

text: e

text: valued,

text: and

text: we

text: distinguish

text: the

text: three

text: cases

text: given

text: by

text: the

text: minimisers

text: of

text: If

text: (x¯

text: (t,

text: j),

text: y)

text: S

text: ∩V

text: d

text: L

text: then

text: ∂V

text: (t,

text: j)

text: y)T

text: P

text: I

text: −I

text: d

text: n

text: n

text: ∂q

text: and

text: Ax¯

text: (t,

text: j)

text: E

text: Bu

text: (t)

text: F

text: d

text: ﬀ

text: e

text: Ay

text: E

text: B(u

text: (t)

text: c

text: (x¯

text: (t,

text: j)

text: y))

text: ﬀ

text: d

text: such

text: that

text: is

text: guaranteed

text: by

text: If

text: (x¯

text: (t,

text: j),

text: y)

text: S

text: ∩V

text: then

text: of

text: Lemma

text: implies

text: G¯(y)

text: (L+MJ)y+H

text: +MK.

text: Consequently

text: d

text: L

text: ∂V

text: P

text: I

text: −(L

text: MJ)

text: ∂q

text: s

text: n

text: and

text: Ax¯

text: (t,

text: j)

text: E

text: Bu

text: (t)

text: d

text: ﬀ

text: Fe(t,

text: x¯d(t,

text: j),

text: y)=

text: Ay+E+B(u

text: (t)−

text: −c

text: s

text: ﬀ

text: with

text: s

text: x¯

text: (t,

text: j)−G¯(y)

text: holds.

text: Hence,

text: we

text: obtain

text: ∂V

text: F

text: (t,

text: x,

text: y)

text: P

text: (Ax¯

text: (t,

text: j)+E

text: +Bu

text: (t)−

text: d

text: ∂q

text: e

text: s

text: d

text: ﬀ

text: (L

text: MJ)Ay

text: (L

text: MJ)E

text: (L

text: MJ)Bu

text: β

text: (t)

text: (L

text: MJ)Bc

text: s

text: With

text: we

text: ﬁnd

text: ﬀ(t)

text: β

text: (t)

text: β

text: (t),

text: such

text: that

text: ∂V

text: F

text: (t,

text: x¯

text: (t,

text: j),

text: y)

text: ∂q

text: e

text: d

text: P

text: (Ax¯

text: (t,

text: j)

text: (I

text: L

text: MJ)(E

text: Bu

text: (t))

text: s

text: d

text: ﬀ

text: (L

text: MJ)Ay

text: β

text: (t)

text: β

text: c

text: s

text: Since

text: y

text: +x¯

text: (t,

text: j)−H

text: −MK)

text: +G¯◦(x¯

text: (t,

text: j)),

text: (which

text: holds

text: d

text: d

text: as

text: z

text: x¯

text: (t,

text: j)

text: z

text: follows

text: from

text: (x¯

text: (t,

text: j),

text: y)

text: S

text: V

text: cf.

text: Lemma

text: we

text: obtain

text: d

text: d

text: L

text: ∂V

text: F

text: (t,

text: x¯

text: (t,

text: j),

text: y)

text: ∂q

text: e

text: d

text: P

text: ((L

text: MJ)A(L

text: β

text: c

text: )s

text: s

text: where

text: we

text: used

text: the

text: design

text: of

text: β

text: Hence,

text: guarantees

text: that

text: holds

text: in

text: this

text: case.

text: Now,

text: we

text: focus

text: on

text: the

text: case

text: (x¯

text: (t,

text: j),

text: y)

text: S

text: V

text: In

text: that

text: case,

text: from

text: of

text: Lemma

text: we

text: observe

text: d

text: L

text: that

text: z

text: y

text: z

text: follows

text: from

text: (x¯

text: (t,

text: j),

text: y)

text: S

text: V

text: cf.

text: Lemma

text: Hence,

text: d

text: L

text: ∂V

text: P

text: (L

text: MJ)

text: −I

text: ∂q

text: s

text: n

text: Agai∈n,

text: when

text: before

text: the

text: jump,

text: V

text: (x,y)

text: e

text: λdvL

text: holds,

text: we

text: conclude

text: that

text: x

text: G(y)

text: vL,

text: such

text: that

text: (x,G(y))

text: as

text: shown

text: in

text: Fig.

text: follows.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 Error Correction in Polynomial Remainder Codes with Non-Pairwise Coprime Moduli and Robust Chinese Remainder Theorem for Polynomials Li Xiao and Xiang-Gen Xia Abstract— This paper investigates polynomial remainder codes with residue codes with pairwise coprime moduli, the residue with non-pairwise coprime moduli. We ﬁrst consider a robust error detection and correction algorithm for residue codes with reconstruction problem for polynomials from erroneous residues non-pairwise coprime moduli is much simpler, and the price when the degrees of all residue errors are assumed small, namely paid for that is an increase in redundancy. Moreover, residue robust Chinese Remainder Theorem (CRT) for polynomials. It basically says that a polynomial can be reconstructed from codes with non-pairwise coprime moduli may be quite effec- erroneous residues such that the degree of the reconstruction tive in providing a wild coverage of “random” errors [24]–[26]. error is upper bounded by τ whenever the degrees of all residue In order to perform reliably polynomial-type operations (e.g., errors are upper bounded by τ, where a sufﬁcient condition for cyclic convolution, correlation, DFT and FFT computations) τ and a reconstruction algorithm are obtained. By releasing the with reduced complexity in digital signal processing systems, constraint that all residue errors have small degrees, another robust reconstruction is then presented when there are multiple residue codes over polynomials (called polynomial remainder unrestricted errors and an arbitrary number of errors with small codes in this paper) with pairwise or non-pairwise coprime degrees in the residues. By making full use of redundancy in polynomial moduli have been investigated as well [29]–[36], moduli, we obtain a stronger residue error correction capability where codewords are residue vectors of polynomials with in the sense that apart from the number of errors that can be degrees in a certain range modulo the moduli and all poly- corrected in the previous existing result, some errors with small degrees can be also corrected in the residues. With this newly nomials are deﬁned over a Galois ﬁeld. Polynomial remainder obtained result, improvements in uncorrected error probability codes are a large class of codes that include BCH codes and burst error correction capability in a data transmission are and Reed-Solomon codes as special cases [27], [28]. Due to illustrated. two important features in residue codes: carry-free arithmetics Index Terms—Burst error correction, error correction codes, and absence of ordered signiﬁcance among the residues, polynomial remainder codes, residue codes, robust Chinese Re- residue error detection and correction technique in residue mainder Theorem (CRT). codes has various applications in, for example, fault-tolerant execution of arithmetic operations in digital processors and in I. INTRODUCTION general digital hardware implementations on computers [10]– T HE Chinese Remainder Theorem (CRT) can uniquely [12], [32], [33], orthogonal frequency division multiplexing determine a large integer from its remainders with respect (OFDM) and code division multiple access (CDMA) based to several moduli if the large integer is less than the least communication systems [13]–[19], and secure distributed data common multiple (lcm) of all the moduli [1], [2]. Based on the storage for wireless networks [20]–[23]. CRT for integers, residue codes with pairwise or non-pairwise In this paper, we focus on polynomial remainder codes with coprime moduli are independently constructed, where code- non-pairwise coprime moduli. Note that a coding theoretic words are residue vectors of integers in a certain range modulo framework for such a class of codes has been proposed in [33], (cid:81) the moduli. More speciﬁcally, a residue code with pairwise co- where the concepts of Hamming weight, Hamming distance, · · · · · · prime moduli m , , m , m , , m consists of residue code distance in polynomial remainder codes are introduced. 1 k k+1 n vectors of integers in the range [0, k m ), where the ﬁrst k It is stated in [33] that a polynomial remainder code with non- moduli form a set of nonredundant mi=od1ulii, and the last n − k pai(cid:98)rwis−e copri(cid:99)me moduli and code distance d can correct up moduli form a set of redundant moduli used for residue error to (d 1)/2 errors in the residues, and a fast residue error (cid:98) (cid:99) detection and correction. Over the past few decades, there has correction algorithm is also presented, where (cid:63) is the ﬂoor been a vast amount of research on residue error correction function. This reconstruction from the error correction method algorithms for such a class of codes. For more details, we refer is accurate but only a few of residues are allowed to have errors the reader to [3]–[9]. By removing the requirement that the and most of residues have to be error-free. The goal of this moduli be pairwise coprime, a residue code with non-pairwise paper is to study robust reconstruction and error correction · · · coprime moduli m , m , , m consists of residue vectors when a few residues have arbitrary errors (called unrestricted 1 2 l · · · of integers in the range [0, lcm(m , m , , m )). Compared errors) similar to [33] and some (or all) of the remaining 1 2 l residues have small errors (i.e., the degrees of errors are small). The authors are with Department of Electrical and Computer Engineer- It is two-fold. One is to study robust reconstruction and the { ing, University of Delaware, Newark, DE 19716, U.S.A. (e-mail: lixiao, } other is to study error correction, i.e., accurate reconstruction, xxia @ee.udel.edu). Their work was supported in part by the Air Force Ofﬁce of Scientiﬁc Research (AFOSR) under Grant FA9550-12-1-0055. when residues have errors.

text: Error

label: title

text: Correction

text: in

text: Polynomial

text: Remainder

text: Codes

text: with

text: Non-Pairwise

text: Coprime

text: Moduli

text: and

text: Robust

text: Chinese

text: Remainder

text: Theorem

text: for

text: Polynomials

text: Li

label: author

text: Xiao

text: and

text: Xiang-Gen

text: Xia

text: Abstract—

text: This

label: abstract

text: paper

text: investigates

text: polynomial

text: remainder

text: codes

text: with

text: residue

text: codes

text: with

text: pairwise

text: coprime

text: moduli,

text: the

text: residue

text: with

text: non-pairwise

text: coprime

text: moduli.

text: We

text: ﬁrst

text: consider

text: a

text: robust

text: error

text: detection

text: and

text: correction

text: algorithm

text: for

text: residue

text: codes

text: with

text: reconstruction

text: problem

text: for

text: polynomials

text: from

text: erroneous

text: residues

text: non-pairwise

text: coprime

text: moduli

text: is

text: much

text: simpler,

text: and

text: the

text: price

text: when

text: the

text: degrees

text: of

text: all

text: residue

text: errors

text: are

text: assumed

text: small,

text: namely

text: paid

text: for

text: that

text: is

text: an

text: increase

text: in

text: redundancy.

text: Moreover,

text: residue

text: robust

text: Chinese

text: Remainder

text: Theorem

text: (CRT)

text: for

text: polynomials.

text: It

text: basically

text: says

text: that

text: a

text: polynomial

text: can

text: be

text: reconstructed

text: from

text: codes

text: with

text: non-pairwise

text: coprime

text: moduli

text: may

text: be

text: quite

text: effec-

text: erroneous

text: residues

text: such

text: that

text: the

text: degree

text: of

text: the

text: reconstruction

text: tive

text: in

text: providing

text: a

text: wild

text: coverage

text: of

text: “random”

text: errors

text: error

text: is

text: upper

text: bounded

text: by

text: τ

text: whenever

text: the

text: degrees

text: of

text: all

text: residue

text: In

text: order

text: to

text: perform

text: reliably

text: polynomial-type

text: operations

text: (e.g.,

text: errors

text: are

text: upper

text: bounded

text: by

text: τ,

text: where

text: a

text: sufﬁcient

text: condition

text: for

text: cyclic

text: convolution,

text: correlation,

text: DFT

text: and

text: FFT

text: computations)

text: τ

text: and

text: a

text: reconstruction

text: algorithm

text: are

text: obtained.

text: By

text: releasing

text: the

text: with

text: reduced

text: complexity

text: in

text: digital

text: signal

text: processing

text: systems,

text: constraint

text: that

text: all

text: residue

text: errors

text: have

text: small

text: degrees,

text: another

text: robust

text: reconstruction

text: is

text: then

text: presented

text: when

text: there

text: are

text: multiple

text: residue

text: codes

text: over

text: polynomials

text: (called

text: polynomial

text: remainder

text: unrestricted

text: errors

text: and

text: an

text: arbitrary

text: number

text: of

text: errors

text: with

text: small

text: codes

text: in

text: this

text: paper)

text: with

text: pairwise

text: or

text: non-pairwise

text: coprime

text: degrees

text: in

text: the

text: residues.

text: By

text: making

text: full

text: use

text: of

text: redundancy

text: in

text: polynomial

text: moduli

text: have

text: been

text: investigated

text: as

text: well

text: moduli,

text: we

text: obtain

text: a

text: stronger

text: residue

text: error

text: correction

text: capability

text: where

text: codewords

text: are

text: residue

text: vectors

text: of

text: polynomials

text: with

text: in

text: the

text: sense

text: that

text: apart

text: from

text: the

text: number

text: of

text: errors

text: that

text: can

text: be

text: degrees

text: in

text: a

text: certain

text: range

text: modulo

text: the

text: moduli

text: and

text: all

text: poly-

text: corrected

text: in

text: the

text: previous

text: existing

text: result,

text: some

text: errors

text: with

text: small

text: degrees

text: can

text: be

text: also

text: corrected

text: in

text: the

text: residues.

text: With

text: this

text: newly

text: nomials

text: are

text: deﬁned

text: over

text: a

text: Galois

text: ﬁeld.

text: Polynomial

text: remainder

text: obtained

text: result,

text: improvements

text: in

text: uncorrected

text: error

text: probability

text: codes

text: are

text: a

text: large

text: class

text: of

text: codes

text: that

text: include

text: BCH

text: codes

text: and

text: burst

text: error

text: correction

text: capability

text: in

text: a

text: data

text: transmission

text: are

text: and

text: Reed-Solomon

text: codes

text: as

text: special

text: cases

text: Due

text: to

text: illustrated.

text: two

text: important

text: features

text: in

text: residue

text: codes:

text: carry-free

text: arithmetics

text: Index

text: Terms—Burst

text: error

text: correction,

text: error

text: correction

text: codes,

text: and

text: absence

text: of

text: ordered

text: signiﬁcance

text: among

text: the

text: residues,

text: polynomial

text: remainder

text: codes,

text: residue

text: codes,

text: robust

text: Chinese

text: Re-

text: residue

text: error

text: detection

text: and

text: correction

text: technique

text: in

text: residue

text: mainder

text: Theorem

text: (CRT).

text: codes

text: has

text: various

text: applications

text: in,

text: for

text: example,

text: fault-tolerant

text: execution

text: of

text: arithmetic

text: operations

text: in

text: digital

text: processors

text: and

text: in

text: I.

text: INTRODUCTION

text: general

text: digital

text: hardware

text: implementations

text: on

text: computers

text: T

text: HE

text: Chinese

text: Remainder

text: Theorem

text: (CRT)

text: can

text: uniquely

text: orthogonal

text: frequency

text: division

text: multiplexing

text: determine

text: a

text: large

text: integer

text: from

text: its

text: remainders

text: with

text: respect

text: (OFDM)

text: and

text: code

text: division

text: multiple

text: access

text: (CDMA)

text: based

text: to

text: several

text: moduli

text: if

text: the

text: large

text: integer

text: is

text: less

text: than

text: the

text: least

text: communication

text: systems

text: and

text: secure

text: distributed

text: data

text: common

text: multiple

text: (lcm)

text: of

text: all

text: the

text: moduli

text: Based

text: on

text: the

text: storage

text: for

text: wireless

text: networks

text: CRT

text: for

text: integers,

text: residue

text: codes

text: with

text: pairwise

text: or

text: non-pairwise

text: In

text: this

text: paper,

text: we

text: focus

text: on

text: polynomial

text: remainder

text: codes

text: with

text: coprime

text: moduli

text: are

text: independently

text: constructed,

text: where

text: code-

text: non-pairwise

text: coprime

text: moduli.

text: Note

text: that

text: a

text: coding

text: theoretic

text: words

text: are

text: residue

text: vectors

text: of

text: integers

text: in

text: a

text: certain

text: range

text: modulo

text: framework

text: for

text: such

text: a

text: class

text: of

text: codes

text: has

text: been

text: proposed

text: in

text: the

text: moduli.

text: More

text: speciﬁcally,

text: a

text: residue

text: code

text: with

text: pairwise

text: co-

text: where

text: the

text: concepts

text: of

text: Hamming

text: weight,

text: Hamming

text: distance,

text: prime

text: moduli

text: m

text: m

text: m

text: m

text: consists

text: of

text: residue

text: code

text: distance

text: in

text: polynomial

text: remainder

text: codes

text: are

text: introduced.

text: k

text: n

text: vectors

text: of

text: integers

text: in

text: the

text: range

text: k

text: m

text: where

text: the

text: ﬁrst

text: k

text: It

text: is

text: stated

text: in

text: that

text: a

text: polynomial

text: remainder

text: code

text: with

text: non-

text: moduli

text: form

text: a

text: set

text: of

text: nonredundant

text: and

text: the

text: last

text: n

text: k

text: moduli

text: and

text: code

text: distance

text: d

text: can

text: correct

text: up

text: moduli

text: form

text: a

text: set

text: of

text: redundant

text: moduli

text: used

text: for

text: residue

text: error

text: to

text: (d

text: errors

text: in

text: the

text: residues,

text: and

text: a

text: fast

text: residue

text: error

text: detection

text: and

text: correction.

text: Over

text: the

text: past

text: few

text: decades,

text: there

text: has

text: correction

text: algorithm

text: is

text: also

text: presented,

text: where

text: is

text: the

text: ﬂoor

text: been

text: a

text: vast

text: amount

text: of

text: research

text: on

text: residue

text: error

text: correction

text: function.

text: This

text: reconstruction

text: from

text: the

text: error

text: correction

text: method

text: algorithms

text: for

text: such

text: a

text: class

text: of

text: codes.

text: For

text: more

text: details,

text: we

text: refer

text: is

text: accurate

text: but

text: only

text: a

text: few

text: of

text: residues

text: are

text: allowed

text: to

text: have

text: errors

text: the

text: reader

text: to

text: By

text: removing

text: the

text: requirement

text: that

text: the

text: and

text: most

text: of

text: residues

text: have

text: to

text: be

text: error-free.

text: The

text: goal

text: of

text: this

text: moduli

text: be

text: pairwise

text: coprime,

text: a

text: residue

text: code

text: with

text: non-pairwise

text: paper

text: is

text: to

text: study

text: robust

text: reconstruction

text: and

text: error

text: correction

text: coprime

text: moduli

text: m

text: m

text: m

text: consists

text: of

text: residue

text: vectors

text: when

text: a

text: few

text: residues

text: have

text: arbitrary

text: errors

text: (called

text: unrestricted

text: l

text: of

text: integers

text: in

text: the

text: range

text: lcm(m

text: m

text: m

text: Compared

text: errors)

text: similar

text: to

text: and

text: some

text: (or

text: all)

text: of

text: the

text: remaining

text: l

text: residues

text: have

text: small

text: errors

text: (i.e.,

text: the

text: degrees

text: of

text: errors

text: are

text: small).

text: The

text: authors

text: are

text: with

text: Department

text: of

text: Electrical

text: and

text: Computer

text: Engineer-

text: It

text: is

text: two-fold.

text: One

text: is

text: to

text: study

text: robust

text: reconstruction

text: and

text: the

text: ing,

text: University

text: of

text: Delaware,

text: Newark,

text: DE

text: U.S.A.

text: (e-mail:

text: lixiao,

text: other

text: is

text: to

text: study

text: error

text: correction,

text: i.e.,

text: accurate

text: reconstruction,

text: xxia

text: @ee.udel.edu).

text: Their

text: work

text: was

text: supported

text: in

text: part

text: by

text: the

text: Air

text: Force

text: Ofﬁce

text: of

text: Scientiﬁc

text: Research

text: (AFOSR)

text: under

text: Grant

text: when

text: residues

text: have

text: errors.


text: srorre detcerrocnu fo ytilibaborP 11 GF(p) is encoded and sent by transmitting the coefﬁcients 100 of the residues of its corresponding polynomial a(x) modulo m (x) as in (26), then, based on residue error correction i 10−1 capability of polynomial remainder codes in Theorem 3, the following results are easily obtained: 10−2 1) Correction of bursts of width not more than η(θ) ≤ 10−3 1.1) when A B, it can correct up to A such bursts; (cid:98) − (cid:99) 1.2) when A > B, it can correct up to B + (A B)/2 10−4 such bursts. 2) Correction of bursts of width not more than m + η(θ) 10−5 (cid:98) (cid:99) ≤ (cid:98) (cid:99) Uncorrected error probability for the decoding algorithm in Section II 2.1) when A/2 B, it can correct up to A/2 such 10−6 AU nthcoeorrreectitceadl eurpropre rp broobuanbdi liinty ( f4o3r) our decoding algorithm in Section V bursts;(cid:98) (cid:99) (cid:98) − A theoretical upper bound in (46) 2.2) when A/2 > B, it can correct up to B + (A (cid:99) 10−170 −4 10−3 10−2 10−1 100 2B)/3 such bursts. Channel bit error probability γ From Theorem 3, the polynomial remainder code with moduli ≤ ≤ m (x) for 1 i L can correct up to A unrestricted errors Fig. 1. Uncorrected error probabilities based on Proposition i and B bounded errors with the remainder error bound η(θ) 2 and Theorem 3: simulations and theoretical upper bounds. in the residues. Fig. 2 shows that an error burst of width not more than η(θ) in (26) can, at most, give rise to a residue with We next investigate the burst error correction capability an error and a residue with a bounded error. So, 1.1) and 1.2) in polynomial remainder codes with non-pairwise coprime are easily obtained. Similarly, from Fig. 2, an error burst of moduli. As a residue a (x) occupies m bits, an error in width not more than m + η(θ) in (26) can, at most, give rise i i this residue would affect up to m bits. In order to express to two residues with errors and one residue with a bounded i (cid:98) (cid:99) ≤ (cid:98) (cid:99) our question more precisely, we assume that all the moduli error. So, when A/2 B, it can only correct up to A/2 · · · (cid:98) (cid:99) m (x), m (x), , m (x) have the same degree m. Then, such bursts. When A/2 > B, in addition to correcting B 1 2 L any error burst of width not more than m + 1 in (26) can bursts of width not more than m + η(θ), the remaining error (cid:98) − (cid:99) affect two residues at most. Similar to the result for polynomial correction capability can correct up to (A 2B)/3 such remainder codes with pairwise coprime moduli in [29], [30], it bursts more. is directly obtained that the polynomial remainder code with Remark 6: In the previous result in [33], a polynomial non-pairwise coprime moduli and code distance d that can remainder code with code distance d can correct up to (cid:98) − (cid:99) (cid:98) − (cid:99) correct up to (d 1)/2 errors in the residues can correct A = (d 1)/2 residue errors. Based on this error correction (cid:98)(cid:98) − (cid:99) (cid:99) (cid:98) (cid:99) up to (d 1)/2 /2 bursts of width not more than m + 1, capability, it can only correct up to A/2 bursts of width not (cid:98) − (cid:99) − (cid:98) (cid:99) or correct one burst of width ( (d 1)/2 1)m + 1. By more than η(θ), or correct up to A/3 bursts of width not Theorem 3, however, we can further improve the capability more than m+η(θ) if η(θ) > 1, which are not as good as the of burst error correction in the polynomial remainder codes above results. (cid:98) − (cid:99) with non-pairwise coprime moduli. Let A = (d 1)/2 and (cid:98) − (cid:99) − (cid:98) − (cid:99) B = (L θ)/2 (d 1)/2 , and we have the following VI. CONCLUSION result. In this paper, we studied polynomial remainder codes with non-pairwise coprime moduli. We ﬁrst considered the robust reconstruction problem from erroneous residues, namely ro- bust CRT for polynomial problem, where all residues are allowed to have errors, but all the errors have to be bounded. A sufﬁcient condition for the robustness bound was obtained, and a reconstruction algorithm was also proposed in the paper. Then, by releasing the constraint that all residue er- rors are bounded, another robust reconstruction was proposed when multiple unrestricted errors and an arbitrary number of bounded errors have occurred in the residues. Finally, Fig. 2. Burst error representations. compared with the previous residue error correction result in polynomial remainder codes, interestingly, our proposed result ≤ ≤ shows that in addition to correcting the number of residue Corollary 1: Let m (x), 1 i L, be L non-pairwise i errors as in [33], some bounded residue errors can be corrected coprime polynomial moduli with the same degree m. Assume as well. With our proposed result in residue error correction, that the code distance of the polynomial remainder code with − better performances in uncorrected error probability and burst the moduli is d. Deﬁne by M(x) with deg (M(x)) > k 1 error correction in a data transmission can be achieved. the least common multiple of all the moduli, and let η(θ) be deﬁned in (23). If a sequence a = (a[1], a[2], · · · , a[k]) over ACKNOWLEDGMENT ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: srorre

font: default

text: detcerrocnu

text: fo

text: ytilibaborP

text: GF(p)

text: is

text: encoded

text: and

text: sent

text: by

text: transmitting

text: the

text: coefﬁcients

text: of

text: the

text: residues

text: of

text: its

text: corresponding

text: polynomial

text: a(x)

text: modulo

text: m

text: (x)

text: as

text: in

text: then,

text: based

text: on

text: residue

text: error

text: correction

text: i

text: capability

text: of

text: polynomial

text: remainder

text: codes

text: in

text: Theorem

text: the

text: following

text: results

text: are

text: easily

text: obtained:

text: Correction

text: of

text: bursts

text: of

text: width

text: not

text: more

text: than

text: η(θ)

text: when

text: A

text: B,

text: it

text: can

text: correct

text: up

text: to

text: A

text: such

text: bursts;

text: when

text: A

text: B,

text: it

text: can

text: correct

text: up

text: to

text: B

text: (A

text: such

text: bursts.

text: Correction

text: of

text: bursts

text: of

text: width

text: not

text: more

text: than

text: m

text: η(θ)

text: Uncorrected

text: error

text: probability

text: for

text: the

text: decoding

text: algorithm

text: in

text: Section

text: II

text: when

text: B,

text: it

text: can

text: correct

text: up

text: to

text: such

text: AU

text: nthcoeorrreectitceadl

text: eurpropre

text: rp

text: broobuanbdi

text: liinty

text: our

text: decoding

text: algorithm

text: in

text: Section

text: V

text: A

text: theoretical

text: upper

text: bound

text: in

text: when

text: B,

text: it

text: can

text: correct

text: up

text: to

text: B

text: (A

text: −4

text: such

text: bursts.

text: Channel

text: bit

text: error

text: probability

text: γ

text: From

text: Theorem

text: the

text: polynomial

text: remainder

text: code

text: with

text: moduli

text: m

text: (x)

text: for

text: i

text: L

text: can

text: correct

text: up

text: to

text: A

text: unrestricted

text: errors

text: Fig.

text: Uncorrected

text: error

text: probabilities

text: based

text: on

text: Proposition

text: i

text: and

text: B

text: bounded

text: errors

text: with

text: the

text: remainder

text: error

text: bound

text: η(θ)

text: and

text: Theorem

text: simulations

text: and

text: theoretical

text: upper

text: bounds.

text: in

text: the

text: residues.

text: Fig.

text: shows

text: that

text: an

text: error

text: burst

text: of

text: width

text: not

text: more

text: than

text: η(θ)

text: in

text: can,

text: at

text: most,

text: give

text: rise

text: to

text: a

text: residue

text: with

text: We

text: next

text: investigate

text: the

text: burst

text: error

text: correction

text: capability

text: an

text: error

text: and

text: a

text: residue

text: with

text: a

text: bounded

text: error.

text: So,

text: and

text: in

text: polynomial

text: remainder

text: codes

text: with

text: non-pairwise

text: coprime

text: are

text: easily

text: obtained.

text: Similarly,

text: from

text: Fig.

text: an

text: error

text: burst

text: of

text: moduli.

text: As

text: a

text: residue

text: a

text: (x)

text: occupies

text: m

text: bits,

text: an

text: error

text: in

text: width

text: not

text: more

text: than

text: m

text: η(θ)

text: in

text: can,

text: at

text: most,

text: give

text: rise

text: i

text: i

text: this

text: residue

text: would

text: affect

text: up

text: to

text: m

text: bits.

text: In

text: order

text: to

text: express

text: to

text: two

text: residues

text: with

text: errors

text: and

text: one

text: residue

text: with

text: a

text: bounded

text: i

text: our

text: question

text: more

text: precisely,

text: we

text: assume

text: that

text: all

text: the

text: moduli

text: error.

text: So,

text: when

text: B,

text: it

text: can

text: only

text: correct

text: up

text: to

text: m

text: (x),

text: m

text: (x),

text: m

text: (x)

text: have

text: the

text: same

text: degree

text: m.

text: Then,

text: such

text: bursts.

text: When

text: B,

text: in

text: addition

text: to

text: correcting

text: B

text: L

text: any

text: error

text: burst

text: of

text: width

text: not

text: more

text: than

text: m

text: in

text: can

text: bursts

text: of

text: width

text: not

text: more

text: than

text: m

text: η(θ),

text: the

text: remaining

text: error

text: affect

text: two

text: residues

text: at

text: most.

text: Similar

text: to

text: the

text: result

text: for

text: polynomial

text: correction

text: capability

text: can

text: correct

text: up

text: to

text: (A

text: such

text: remainder

text: codes

text: with

text: pairwise

text: coprime

text: moduli

text: in

text: it

text: bursts

text: more.

text: is

text: directly

text: obtained

text: that

text: the

text: polynomial

text: remainder

text: code

text: with

text: Remark

text: In

text: the

text: previous

text: result

text: in

text: a

text: polynomial

text: non-pairwise

text: coprime

text: moduli

text: and

text: code

text: distance

text: d

text: that

text: can

text: remainder

text: code

text: with

text: code

text: distance

text: d

text: can

text: correct

text: up

text: to

text: correct

text: up

text: to

text: (d

text: errors

text: in

text: the

text: residues

text: can

text: correct

text: A

text: (d

text: residue

text: errors.

text: Based

text: on

text: this

text: error

text: correction

text: up

text: to

text: (d

text: bursts

text: of

text: width

text: not

text: more

text: than

text: m

text: capability,

text: it

text: can

text: only

text: correct

text: up

text: to

text: bursts

text: of

text: width

text: not

text: or

text: correct

text: one

text: burst

text: of

text: width

text: (d

text: By

text: more

text: than

text: η(θ),

text: or

text: correct

text: up

text: to

text: bursts

text: of

text: width

text: not

text: Theorem

text: however,

text: we

text: can

text: further

text: improve

text: the

text: capability

text: more

text: than

text: m+η(θ)

text: if

text: η(θ)

text: which

text: are

text: not

text: as

text: good

text: as

text: the

text: of

text: burst

text: error

text: correction

text: in

text: the

text: polynomial

text: remainder

text: codes

text: above

text: results.

text: with

text: non-pairwise

text: coprime

text: moduli.

text: Let

text: A

text: (d

text: and

text: B

text: (L

text: (d

text: and

text: we

text: have

text: the

text: following

text: VI.

text: CONCLUSION

text: result.

text: In

text: this

text: paper,

text: we

text: studied

text: polynomial

text: remainder

text: codes

text: with

text: non-pairwise

text: coprime

text: moduli.

text: We

text: ﬁrst

text: considered

text: the

text: robust

text: reconstruction

text: problem

text: from

text: erroneous

text: residues,

text: namely

text: ro-

text: bust

text: CRT

text: for

text: polynomial

text: problem,

text: where

text: all

text: residues

text: are

text: allowed

text: to

text: have

text: errors,

text: but

text: all

text: the

text: errors

text: have

text: to

text: be

text: bounded.

text: A

text: sufﬁcient

text: condition

text: for

text: the

text: robustness

text: bound

text: was

text: obtained,

text: and

text: a

text: reconstruction

text: algorithm

text: was

text: also

text: proposed

text: in

text: the

text: paper.

text: Then,

text: by

text: releasing

text: the

text: constraint

text: that

text: all

text: residue

text: er-

text: rors

text: are

text: bounded,

text: another

text: robust

text: reconstruction

text: was

text: proposed

text: when

text: multiple

text: unrestricted

text: errors

text: and

text: an

text: arbitrary

text: number

text: of

text: bounded

text: errors

text: have

text: occurred

text: in

text: the

text: residues.

text: Finally,

text: Fig.

text: Burst

text: error

text: representations.

text: compared

text: with

text: the

text: previous

text: residue

text: error

text: correction

text: result

text: in

text: polynomial

text: remainder

text: codes,

text: interestingly,

text: our

text: proposed

text: result

text: shows

text: that

text: in

text: addition

text: to

text: correcting

text: the

text: number

text: of

text: residue

text: Corollary

text: Let

text: m

text: (x),

text: i

text: L,

text: be

text: L

text: non-pairwise

text: i

text: errors

text: as

text: in

text: some

text: bounded

text: residue

text: errors

text: can

text: be

text: corrected

text: coprime

text: polynomial

text: moduli

text: with

text: the

text: same

text: degree

text: m.

text: Assume

text: as

text: well.

text: With

text: our

text: proposed

text: result

text: in

text: residue

text: error

text: correction,

text: that

text: the

text: code

text: distance

text: of

text: the

text: polynomial

text: remainder

text: code

text: with

text: better

text: performances

text: in

text: uncorrected

text: error

text: probability

text: and

text: burst

text: the

text: moduli

text: is

text: d.

text: Deﬁne

text: by

text: M(x)

text: with

text: deg

text: (M(x))

text: k

text: error

text: correction

text: in

text: a

text: data

text: transmission

text: can

text: be

text: achieved.

text: the

text: least

text: common

text: multiple

text: of

text: all

text: the

text: moduli,

text: and

text: let

text: η(θ)

text: be

text: deﬁned

text: in

text: If

text: a

text: sequence

text: a

text: a[k])

text: over

text: ACKNOWLEDGMENT

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: In Section , we gain control of higher homology by also allowing ﬁxed points. The manifold quotient condition tightly constrains the ﬁxed set. However, we canonically obtain a smooth manifold quotient from a codimension-4 ﬁxed set whose meridians are 3-spheres with the Hopf circle action: The meridians descend to meridian 2-spheres, so the ﬁxed set descends to have codimension three. The quotient map has a quadratic local model, and can be thought of as a generalization of a 2-fold branched covering map. To construct our examples, we consider quotient manifolds as handlebodies (with open handles). C R → Calcut exhibited Pm as the quotient of a ﬂow on 2m+1 by starting with the Hopf ﬁbration S2m+1 C C Pm and removing a point from the domain. Note that Pm is built with a handle of each even index R through 2m, but the lifts of all but the 0-handle are “invisible” in the domain 2m+1. Since quotient maps of ﬂows are always surjective on π (when the quotient is a manifold and hence semilocally simply 1 connected), it is impossible to have 1-handles that are invisible in this manner. However, close inspection of the invisible 2-handle in Calcut’s example reveals how it functions, allowing us to construct such 2-handles more generally. We investigate such invisible 2-handles in Section . Then we construct higher- → C index handles in Section by replacing the Hopf map S3 P1 = S2 by its iterated suspensions. The resulting invisible k-handles have nonempty ﬁxed-point sets of the sort described previously, but allow us to control higher homology of the smooth quotient. It remains an open question whether the higher-index C handles of the Hopf map to Pm can be exploited to yield ﬁxed-point free ﬂows with invisible k-handles for even k > 2 (see Section ). Our main theorems assert that if an n-manifold V is obtained from another manifold U by attaching × R a layer of open handles of index at least two, then it is the quotient of a ﬂow on U . (See The- orem 2.3 for 2-handles and ﬁxed-point free ﬂows, and Theorem 3.1 in general.) We immediately see R (Corollaries 2.4 and 3.2(a)) that when U is contractible, V is the quotient of some ﬂow on n+1. This gives almost complete control of the homology and intersection pairing of quotient manifolds of ﬂows on R n+1 (Example 2.5(a) and Corollary 3.2(b)) although they must be simply connected. We also obtain ≥ every compact homotopy n-sphere (n 2) as such a quotient (Examples 3.4(a,c)). Section gives further applications of invisible 2-handles, which are expanded to higher homology in Section (Corollary 3.2 and Remarks 3.3). Corollary 2.6 gives a counterpoint to π -surjectivity of quotient maps: Every epimorphism 1 of countably generated groups is induced by the quotient map of some ﬂow with manifold quotient (of × R ﬁxed dimension four or larger), and for many manifolds U, there are such ﬂows on U realizing all quotients of π (U). Corollary 2.7 observes that every oriented n-manifold admitting a proper Morse 1 R − × R − function, bounded below, whose indices are at most two, is a quotient of a ﬂow on ( 2 S) n 1 for some discrete, closed S, with a similar result in the nonorientable case. In particular, every oriented R surface (possibly closed or with inﬁnite topology) is a quotient of a ﬂow on 3 minus parallel lines, every R oriented, open 3-manifold is a quotient of 4 minus parallel planes, and various related results hold for 4- and 5-manifolds (Examples 2.8). The tools developed in this paper allow a deeper study of exotic ﬂows of the sort ﬁrst introduced in dimension ﬁve by Arnol’d. We call two ﬂows topologically (respectively smoothly) equivalent if they are conjugate by a homeomorphism (resp. diﬀeomorphism). “Most” smooth 4-manifolds X have inﬁnitely many diﬀeomorphism types of exotic smoothings (uncountably many in the noncompact case), such that × R the corresponding smoothings on X are diﬀeomorphic. As Arnol’d observed, we can interpret these × R as topologically equivalent but smoothly inequivalent ﬂows on the 5-manifolds X , distinguished by the diﬀeomorphism types of their quotients. Since these are product ﬂows, their quotient maps are R homotopy equivalences. In contrast, we show (Example 2.5(b), cf. also Corollary 3.5) that 5 has inﬁnitely many topologically equivalent but smoothly inequivalent ﬂows with quotient realizing any preassigned intersection form, and some forms are realized by uncountable families. All of these 5-dimensional families, R like those of Arnol’d, are unstable under Cartesian product with . That is, the ﬂows within each family R become smoothly equivalent if we take their product with the ﬂow of velocity zero on (or any other manifold of positive dimension). Using handles of higher index (Examples 3.4) we can instead construct R R ﬁnite families of exotic ﬂows on n+1 that are stable under product with (although their behavior under R iterated stabilization, i.e., product with m, is less clear). On the other hand, Example 3.4(e) exhibits unsmoothable topological ﬂows on smooth manifolds, i.e., 1-parameter groups of homeomorphisms that 2

text: In

text: Section

text: we

text: gain

text: control

text: of

text: higher

text: homology

text: by

text: also

text: allowing

text: ﬁxed

text: points.

text: The

text: manifold

text: quotient

text: condition

text: tightly

text: constrains

text: the

text: ﬁxed

text: set.

text: However,

text: we

text: canonically

text: obtain

text: a

text: smooth

text: manifold

text: quotient

text: from

text: a

text: ﬁxed

text: set

text: whose

text: meridians

text: are

text: with

text: the

text: Hopf

text: circle

text: action:

text: The

text: meridians

text: descend

text: to

text: meridian

text: so

text: the

text: ﬁxed

text: set

text: descends

text: to

text: have

text: codimension

text: three.

text: The

text: quotient

text: map

text: has

text: a

text: quadratic

text: local

text: model,

text: and

text: can

text: be

text: thought

text: of

text: as

text: a

text: generalization

text: of

text: a

text: branched

text: covering

text: map.

text: To

text: construct

text: our

text: examples,

text: we

text: consider

text: quotient

text: manifolds

text: as

text: handlebodies

text: (with

text: open

text: handles).

text: C

text: R

text: Calcut

text: exhibited

text: Pm

text: as

text: the

text: quotient

text: of

text: a

text: ﬂow

text: on

text: by

text: starting

text: with

text: the

text: Hopf

text: ﬁbration

text: C

text: C

text: Pm

text: and

text: removing

text: a

text: point

text: from

text: the

text: domain.

text: Note

text: that

text: Pm

text: is

text: built

text: with

text: a

text: handle

text: of

text: each

text: even

text: index

text: R

text: through

text: but

text: the

text: lifts

text: of

text: all

text: but

text: the

text: are

text: “invisible”

text: in

text: the

text: domain

text: Since

text: quotient

text: maps

text: of

text: ﬂows

text: are

text: always

text: surjective

text: on

text: π

text: (when

text: the

text: quotient

text: is

text: a

text: manifold

text: and

text: hence

text: semilocally

text: simply

text: connected),

text: it

text: is

text: impossible

text: to

text: have

text: that

text: are

text: invisible

text: in

text: this

text: manner.

text: However,

text: close

text: inspection

text: of

text: the

text: invisible

text: in

text: Calcut’s

text: example

text: reveals

text: how

text: it

text: functions,

text: allowing

text: us

text: to

text: construct

text: such

text: more

text: generally.

text: We

text: investigate

text: such

text: invisible

text: in

text: Section

text: Then

text: we

text: construct

text: higher-

text: C

text: index

text: handles

text: in

text: Section

text: by

text: replacing

text: the

text: Hopf

text: map

text: by

text: its

text: iterated

text: suspensions.

text: The

text: resulting

text: invisible

text: k-handles

text: have

text: nonempty

text: ﬁxed-point

text: sets

text: of

text: the

text: sort

text: described

text: previously,

text: but

text: allow

text: us

text: to

text: control

text: higher

text: homology

text: of

text: the

text: smooth

text: quotient.

text: It

text: remains

text: an

text: open

text: question

text: whether

text: the

text: higher-index

text: C

text: handles

text: of

text: the

text: Hopf

text: map

text: to

text: Pm

text: can

text: be

text: exploited

text: to

text: yield

text: ﬁxed-point

text: free

text: ﬂows

text: with

text: invisible

text: k-handles

text: for

text: even

text: k

text: (see

text: Section

text: Our

text: main

text: theorems

text: assert

text: that

text: if

text: an

text: n-manifold

text: V

text: is

text: obtained

text: from

text: another

text: manifold

text: U

text: by

text: attaching

text: R

text: a

text: layer

text: of

text: open

text: handles

text: of

text: index

text: at

text: least

text: two,

text: then

text: it

text: is

text: the

text: quotient

text: of

text: a

text: ﬂow

text: on

text: U

text: (See

text: The-

text: orem

text: for

text: and

text: ﬁxed-point

text: free

text: ﬂows,

text: and

text: Theorem

text: in

text: general.)

text: We

text: immediately

text: see

text: R

text: (Corollaries

text: and

text: that

text: when

text: U

text: is

text: contractible,

text: V

text: is

text: the

text: quotient

text: of

text: some

text: ﬂow

text: on

text: This

text: gives

text: almost

text: complete

text: control

text: of

text: the

text: homology

text: and

text: intersection

text: pairing

text: of

text: quotient

text: manifolds

text: of

text: ﬂows

text: on

text: R

text: (Example

text: and

text: Corollary

text: although

text: they

text: must

text: be

text: simply

text: connected.

text: We

text: also

text: obtain

text: every

text: compact

text: homotopy

text: n-sphere

text: (n

text: as

text: such

text: a

text: quotient

text: (Examples

text: Section

text: gives

text: further

text: applications

text: of

text: invisible

text: which

text: are

text: expanded

text: to

text: higher

text: homology

text: in

text: Section

text: (Corollary

text: and

text: Remarks

text: Corollary

text: gives

text: a

text: counterpoint

text: to

text: π

text: -surjectivity

text: of

text: quotient

text: maps:

text: Every

text: epimorphism

text: of

text: countably

text: generated

text: groups

text: is

text: induced

text: by

text: the

text: quotient

text: map

text: of

text: some

text: ﬂow

text: with

text: manifold

text: quotient

text: (of

text: R

text: ﬁxed

text: dimension

text: four

text: or

text: larger),

text: and

text: for

text: many

text: manifolds

text: U,

text: there

text: are

text: such

text: ﬂows

text: on

text: U

text: realizing

text: all

text: quotients

text: of

text: π

text: (U).

text: Corollary

text: observes

text: that

text: every

text: oriented

text: n-manifold

text: admitting

text: a

text: proper

text: Morse

text: R

text: R

text: function,

text: bounded

text: below,

text: whose

text: indices

text: are

text: at

text: most

text: two,

text: is

text: a

text: quotient

text: of

text: a

text: ﬂow

text: on

text: S)

text: n

text: for

text: some

text: discrete,

text: closed

text: S,

text: with

text: a

text: similar

text: result

text: in

text: the

text: nonorientable

text: case.

text: In

text: particular,

text: every

text: oriented

text: R

text: surface

text: (possibly

text: closed

text: or

text: with

text: inﬁnite

text: topology)

text: is

text: a

text: quotient

text: of

text: a

text: ﬂow

text: on

text: minus

text: parallel

text: lines,

text: every

text: R

text: oriented,

text: open

text: is

text: a

text: quotient

text: of

text: minus

text: parallel

text: planes,

text: and

text: various

text: related

text: results

text: hold

text: for

text: and

text: (Examples

text: The

text: tools

text: developed

text: in

text: this

text: paper

text: allow

text: a

text: deeper

text: study

text: of

text: exotic

text: ﬂows

text: of

text: the

text: sort

text: ﬁrst

text: introduced

text: in

text: dimension

text: ﬁve

text: by

text: Arnol’d.

text: We

text: call

text: two

text: ﬂows

text: topologically

text: (respectively

text: smoothly)

text: equivalent

text: if

text: they

text: are

text: conjugate

text: by

text: a

text: homeomorphism

text: (resp.

text: diﬀeomorphism).

text: “Most”

text: smooth

text: X

text: have

text: inﬁnitely

text: many

text: diﬀeomorphism

text: types

text: of

text: exotic

text: smoothings

text: (uncountably

text: many

text: in

text: the

text: noncompact

text: case),

text: such

text: that

text: R

text: the

text: corresponding

text: smoothings

text: on

text: X

text: are

text: diﬀeomorphic.

text: As

text: Arnol’d

text: observed,

text: we

text: can

text: interpret

text: these

text: R

text: as

text: topologically

text: equivalent

text: but

text: smoothly

text: inequivalent

text: ﬂows

text: on

text: the

text: X

text: distinguished

text: by

text: the

text: diﬀeomorphism

text: types

text: of

text: their

text: quotients.

text: Since

text: these

text: are

text: product

text: ﬂows,

text: their

text: quotient

text: maps

text: are

text: R

text: homotopy

text: equivalences.

text: In

text: contrast,

text: we

text: show

text: (Example

text: cf.

text: also

text: Corollary

text: that

text: has

text: inﬁnitely

text: many

text: topologically

text: equivalent

text: but

text: smoothly

text: inequivalent

text: ﬂows

text: with

text: quotient

text: realizing

text: any

text: preassigned

text: intersection

text: form,

text: and

text: some

text: forms

text: are

text: realized

text: by

text: uncountable

text: families.

text: All

text: of

text: these

text: families,

text: R

text: like

text: those

text: of

text: Arnol’d,

text: are

text: unstable

text: under

text: Cartesian

text: product

text: with

text: That

text: is,

text: the

text: ﬂows

text: within

text: each

text: family

text: R

text: become

text: smoothly

text: equivalent

text: if

text: we

text: take

text: their

text: product

text: with

text: the

text: ﬂow

text: of

text: velocity

text: zero

text: on

text: (or

text: any

text: other

text: manifold

text: of

text: positive

text: dimension).

text: Using

text: handles

text: of

text: higher

text: index

text: (Examples

text: we

text: can

text: instead

text: construct

text: R

text: R

text: ﬁnite

text: families

text: of

text: exotic

text: ﬂows

text: on

text: that

text: are

text: stable

text: under

text: product

text: with

text: (although

text: their

text: behavior

text: under

text: R

text: iterated

text: stabilization,

text: i.e.,

text: product

text: with

text: m,

text: is

text: less

text: clear).

text: On

text: the

text: other

text: hand,

text: Example

text: exhibits

text: unsmoothable

text: topological

text: ﬂows

text: on

text: smooth

text: manifolds,

text: i.e.,

text: groups

text: of

text: homeomorphisms

text: that