A reflection on Software Engineering in HEP

High Energy Physics (HEP) has been making very extensive usage of computers to achieve its research goals. Fairly large program suites have been developed, maintained and used over the years and it is fair to say that, overall, HEP has been successful in software development. Yet, HEP software development has not used classical Software Engineering techniques, which have been invented and refined to help the production of large programmes. In this paper we will review the development of HEP code with its strengths and weaknesses. Using several well-known HEP software projects as examples, we will try to demonstrate that our community has used a form of Software Engineering, albeit in an informal manner. The software development techniques employed in these projects are indeed very close in many aspects to the modern tendencies of Software Engineering itself, in particular the so-called “agile technologies”. The paper will conclude with an outlook on the future of software development in HEP.

Introduction
Modern HEP experiments have software suites consisting of O(10 7 ) lines of code written in fairly powerful (and complex!) languages, such as C++, Java and Perl. In general, HEP has been quite successful at developing its own software. A quote attributed, probably apocryphally, to S. Ting, 1976 Physics Nobel Prise winner, is "no experiment ever failed for its software".
In spite of its rather honourable record, HEP has never claimed to use, nor has it used on a large scale, traditional Software Engineering methods, which have been specifically conceived in order to facilitate the production of large programs. However it is our opinion that some intuitive Software Engineering was applied without ever being formalised. Failure to recognise this led to a complicated and not very efficient relationship with Software Engineering and software engineers, that still continues today. This paper will provide some elements of explanation of how this could happen, and what are the reasons behind this apparent contradiction. A more detailed account of this matter can be found in a recently published book [1].

Traditional Software Engineering in HEP
Several generations of successful HEP experiments have produced complex software systems. These have been maintained over the years, adapting to changes in the detector, the replacement of the population of users and developers, and the evolution of the basic technologies of hardware, operating systems and data storage media. Non-professional programmers with no formal Software Engineering training have successfully done all this. Was this madness and pure beginners' luck or is there method in it?

Traditional Software Engineering
Writing large programs has always been recognised as a problematic activity. Since fifty years [2] scientists are trying to address the fact that "Software projects finish late, they run over budget and their products are unreliable" [3]. This has led to the development of an entire discipline that is known as Software Engineering.
The fundamental predicate of Software Engineering is that solid engineering principles should be applied to the production of software in order to transform it into a more predictable and efficient activity. As one can see this is more an objective than a definition, which is moreover based on a questionable assumption on the existence and field of application of "solid engineering methods".
Unfortunately it is seems to be an unavoidable fact of life that any program, once it is tried out in reality, needs to be changed to conform to its intended usage and behaviour. Confronted with change, traditional Software Engineering tried to devise a strategy consistent with the supposed similarity between the software production activity and the engineering processes that, as we have seen, constitutes its founding analogy. Change had to be avoided or, at least, disciplined and controlled via a formal process.
In very broad terms, the strategy devised by classical Software Engineering to achieve its objective of introducing predictability and efficiency in software production, has been to plan exhaustively and in detail the software production process, and to divide it into a series of clearly defined and well-controlled steps, which could be planned in advance. One condition for the success of this strategy is to minimise the ambiguity with which information is moved from one step to the next. Communication tends to be in the form of documents which try to be exhaustive and as detailed as possible in their attempt to cover all the aspects of each phase in the process in order to minimise the need of subsequent changes. This process tends to become quite burdensome and the "overhead" with respect to the software writing activity itself may be substantial. However this could pay off if the objective, i.e. the reduction of the occurrence of change, were attained.
Unfortunately such a process tends to create a situation where the cost of change grows faster than the likeliness of change is reduced. When so many formal steps are involved and so many documents have to be modified and kept consistent between each other, that even the smallest change may be the cause of substantial expense or delays. The net result is to make change slightly less likely but much more expensive with little or no gain.
To be fair, in some application domains there is a reasonable chance to capture the essence of the problem and to reach a full specification of the process with an effective reduction of late change. But these applications tend to be few and, as we will see later on, almost none are to be found in the domain of HEP research.
It can be said that classical Software Engineering in the form of High Ceremony Processes (HCP) did not yield the expected results. In general, the inadequacy of these methods is becoming more and more evident in the e-Business era, when change can no longer be considered an accident, but it has to be regarded as the norm. Software Engineering has its crisis too. In fact many university syllabi on Software Engineering start with the Software Engineering Crisis.
One of the major dangers of the application of HCP Software Engineering to a software project comes from its tendency to adapt reality to its method rather than the opposite. The trouble with HCP Software Engineering is that the elaboration of a plan is very expensive. If reality does not follow "The Plan", the cost of the elaboration of an alternative strategy may simply be prohibitive. It is often the case that, at this point, the entire HCP construction collapses like a house of cards. All divisions of work, established roles, documents, plans, dictionaries and the like suddenly become useless and their remnants stay as a cumbersome legacy that hinders possible correcting actions. The failure of "The Plan" leaves the project with no plan and it then enters a no-man's-land where time-scales and costs-to-completion become unpredictable.
The effects are the more serious the earlier this happens during the lifetime of the project. And in turn, the heavier and more rigid the project, the greater the likelihood that reality will not follow at an early stage. This has come to be commonly denoted by the sentence "too much process kills the process".
One of the keys of the problem probably lies in the deceptive ease with which software can be written, rewritten and modified. In spite of this, the intrinsic time taken by writing a large piece of code is just a small part of the cost of bringing this code into production. Another problem lies in the fact that at the core of applying "solid engineering methods" to software development is the assumption that a personal creative activity, which often software development is, can be transferred into an industrial process.
At this point, however, the above account of classical Software Engineering's status should be tempered with some of its positive aspects. Information Technology revolution at large has changed our world in a way that was not even imaginable only twenty or thirty years ago. No method of software development could have survived this fast-paced evolution without becoming obsolete. Even if we cannot point to a single Software Engineering method that can be said to capture the essence of software development or that proposes a strategy that works, at some level, in most cases, the collective reflection on software development operated by Software Engineering has been invaluable to understand this activity which is at the heart of the Information Technology revolution and it has certainly contributed to it in many ways.
The trouble is that Software Engineering has been offering interesting forays into a very complex field whereas the software industry needs effective strategies for software development. This complex field is at the heart of our society, constantly changing and evolving and still largely unknown; but, and for very good reasons, it has produced no practical recipe that would yield a predictable result.

Classical Software Engineering in HEP
The introduction of Software Engineering methods to the industry eventually attracted the research sector's attention as well. At CERN, for instance, every new method and formalism that appeared over the years has been tried out. Scores of computer scientists have tried to apply these methods with no noticeable impact on HEP software at large, in spite of the time and resources invested. None of the results obtained in this way have come even close to the success and robustness of CERNLIB [4] (and in particular PAW [5] and GEANT 3 [6]), developed over the years with "amateurish" methods, or of ROOT [7], the spiritual heir of CERNLIB.
As we have seen, it does not come as a surprise that classical Software Engineering has not worked as advertised for HEP. It can hardly be claimed that it has worked anywhere as advertised. However what is perhaps surprising is the fact that the software projects where traditional Software Engineering has been adopted, or at least attempted, are amongst the less successful ones of the history of HEP software.
Our interpretation of this is that, over the years, HEP had developed a methodology for software development that was both adequate to its environment and reasonably effective. What these projects did was not to introduce some methodology in the development of HEP software, but rather to replace an existing methodology, which, as we will see, was never formalised or properly described, with one, well represented in the literature, but rather inappropriate for our environment.

THE HEP software development environment
The problems that software designers are called upon to solve in HEP have some specific features that differentiate them from those of an industrial environment. The purpose of industry is to produce goods, products and services and bring them to market. The technologies involved are, in most of the cases, mature and well understood. Marketing and selling implies knowledge of the customer needs and the capacity of maintaining a quality standard for all goods that are sold. The output is measurable in terms of quantity and revenue. Late discovery of flaws is expensive and may seriously harm the image of the manufacturer.
In the research environment in general, and in HEP in particular, nearly all these points are overturned. Our general objective is to acquire knowledge. Not only is what we research still unknown, but means to achieve our objectives may not be available yet, and their acquisition may be part of the research activity itself. We are constantly required to innovate, in order to provide tools and methods that current technology cannot supply.

Software Engineering in HEP
The heart of any Software Engineering method is the attempt to control the impact and the cost of change. Surprisingly enough the idea that all software systems can be designed first and then implemented has seduced several people and the very fact that it is merely a mental model implying a gross simplification of reality seems to escape the majority.
In some sense HEP has always lived in a situation where change was unavoidable at any moment. As we have explained before, some requirements evolve and become clear only during the deployment of software and its use. New ideas are born, which could not have existed if physicists did not experiment with the software. The drive to buy the cheapest possible hardware and the necessity to use existing computing equipment in the collaborating institutions, as they join the experiment, impose to follow the continue diversification and evolution of the computers and operating systems. Once the detector is built, change comes from the need to experiment new ideas and to adapt to unforeseen experimental conditions and to the modifications and upgrades of the apparatus.
If change cannot be avoided, then the economy of change must be reconsidered. The axiom that late change is a disaster needs to be challenged and a methodology that does not allow the cost of change to increase exponentially with time needs to be implemented. If this approach is taken, then sometimes even deferring implementation, and thus creating the possibility of a future change, can be the winning strategy, as the time to implement a given feature may never come. In this case, starting with a minimal design and then evolving it may be much more effective than spending a large amount of time designing the system while the requirements are still unclear.
Over the years HEP has developed a self-styled method that, within the constraints and relative to its objectives, has been surprisingly successful. What computer scientists have had difficulties appreciating is that HEP is an environment where a well adapted method is applied instinctively but successfully to the projects. What is peculiar of HEP is that this methodology is transmitted via "oral" tradition and it has never been formalised. This situation is far from ideal, as knowledge must be abstracted and formalised in order to be properly communicated and to evolve.
HEP development strategy manifestly can cope with change. The Large Electron Positron (LEP)-era experiments started when the dominant computing platforms were mainframes, and the total computing needs estimated for LEP were less than the power of a modern laptop. Yet the LEP software has been ported and adapted over all the technology revolutions intervened over twenty years, and the user investment has been protected. HEP has taken advantage of every piece of inexpensive hardware that hit the market with no disruption in the production of results. The same code that was running twenty years ago on mainframes and on the first VAXes is now running on the latest CPUs with little modification. We believe it is important to analyse and understand the reasons for this undeniable success to see how these can be leveraged for the new generation of experiments.
The main feature of the HEP development method is the apparent absence of design. Indeed the most successful HEP projects started with a very precise initial idea guiding the development. Developers and users "knew what they wanted" because they knew what they missed in the past and what they would have liked to have. This is not very precise but to any Software Engineer's despair, it is as precise as you can make it without imposing useless constraints and without inventing details that most probably you will have to throw away, without wasting time. The objective or "plot" is clear, although sometimes difficult to express and formalise. This initial plot, or metaphor, becomes common ownership of the community of physicist users, and guides the evolution of the system. The actual code is written usually quickly in accordance with the objectives of the project, and it is quickly delivered to the community of users, who are very active in testing it because it answers their immediate needs.
Once started in this way, the software naturally goes through development cycles. The most important features are the ones on which the developers work first, because they are the ones most in demand by the community. Somehow, in the best cases, it all happens in the right way because there is a common culture of the product, the moral of the initial plot, which is shared by the community. Users usually complain vocally, but constructively, and they insist on using the product. Developers implement the most wanted features. Advanced users provide pieces of code, following the style and the philosophy of the product, that most of the time can be just "slotted" in place and become part of the common code-base.
The community that feels collectively responsible drives the code development. Parallel developments often merge into a single product. When necessary, re-factoring or even massive redesign happens. New releases appear quite frequently, and the version under development is constantly available to guinea-pig users or to those who desperately need the new features.
Progress is guided by mutual respect, dialogue and understanding. Most of the communication happens via e-mail and it is not infrequent that some of the major developers meet only a few times in their life. Major redesigns are carried out with the responsibility to protect the investment of existing users, while paving the way for further evolution. This is not the description of a dreamy future. This has been the day-by-day story of the CERN Program Library since then. Other products, where the design-first method has been used, either have never seen the day (E. Pagiola's GEM in the 70's) or had difficulties entering production (e.g.

GEANT 4 [8]).
In what follows we will see some of the most important aspects of the HEP software development cycle in greater detail.

The fine art of releasing
One of the most delicate points of the development of a software project in HEP is the process of delivering (releasing) new versions of a product (including the first one!) to the users. HEP has developed a rather sophisticated procedure for doing this, that in many ways is central to its own development process and that is instructive to examine in more depth.
The reason that the release process is of paramount importance in the HEP software development cycle is that, as we have seen before, requirements are not all and not completely defined at the beginning of the development. Therefore, as the understanding of the requirements becomes clearer and new requirements are added, new versions of the software, sometimes with substantial changes, have to be brought to the users. The acceptance of change in the development process which characterise the HEP development strategy, as opposed to the traditional HCP Software Engineering, implies that any product will go through several releases during its life-cycle.
The first release has special importance. Usually a product is developed when there is a need for it, therefore the user community has expectations and a genuine need to use it in its day-to-day work. Delaying the release too much may force the user community into using some alternative product and then becoming entrenched in it. Early release is important: there is a window of opportunity that should not be missed due to a late release. Also, as changes will certainly be requested, early release when the code base is still limited will make substantial changes of direction easier. Late releases tend to make developers less receptive to requests for major changes in architecture and direction, and we have often seen such "original sins" having long-haul consequences on the life-cycle of the software product. There is a danger in early releases as well. If the product is too immature or offers too little functionality with respect to the intended use, it risks disappointing the users who therefore will try it only once. Subsequent releases follow a similar logic with the distinctive feature of being rather frequent. "Release often, release early" is the punch line, and the necessity of this follows directly from the dynamics of the development that we have explained above. As requirements "trickle" in during the project development, frequent releases are necessary to make sure that the production version of the product satisfies a large fraction of users. Also, in the absence of a "master plan", constant "user verification" of the changes is needed in order to keep corrections small and not disruptive.
Failure to follow this simple recipe has usually been the symptom of a malfunctioning project. Moreover, this is a self-catalysing process. The longer the release time, the larger the number of changes. In such a situation it quickly becomes impossible for the users to simply "replace" the working version with the new one, because the impact of a large number of changes cannot be easily estimated, and substantial backward incompatibilities may have crept into the system. This tends to require extra checking and tests, and may lead to the necessity to expose the system to the users in parallel with the current version for a long time. This makes administration heavier and user interaction more complicated. In a fixed-size developer team, the necessary resources are subtracted from development. Moreover, if the differences between the current and the new version are significant, few users will have the time or willingness to test the new version, with a reduction of valid feedback. This in turn slows down the rate at which the new version improves to meet user needs, which creates a vicious circle.
When this situation arises, there are essentially five major handles on which to act in order to break the stalemate and recover, already described by.
Money. Sometimes buying better and faster machines, rewarding developers with cool laptops or installing fancy junk food vending machine in the developers' corridor might help. In most cases however the time derivative of the improvements that these measures yield is smaller (if positive!) than the degradation of the situation due to slipping release dates. Given the resource-constrained nature of most HEP experiments, depending essentially on public funding and usually chronically understaffed and underfunded, this option is not readily available to ailing HEP software projects.
Time. If the release date cannot be met, then delaying it is the most natural reaction. However very often it is the worst option too, because as time passes, new requirements arise which, because the release is delayed anyway, and because it would look very bad if they were not introduced by the time finally the code is released tend to be introduced. Unfortunately this delays the release even further and it is often the starting point of the vicious cycle. We have seen this happen very frequently in HEP, where even mission-critical products have seen substantial delay in their release. The peculiarity of HEP in this respect is that timing is governed by the experimental apparatus (accelerator and detector). By the time the RAW data start flowing, users will make use of whatever product is there, or will force the project to deliver the product. In the best case this will yield a working product with a reduced scope, in the worst, a partially working product which will address the user requirements only partially.
People. It is well known by now that adding people to a project which is late usually makes it later [9]. Nevertheless also this seems to be the most common corrective action taken when a project is in crisis. In HEP this action can be particularly damaging because of the financial and sociological constraints of most HEP experiments and project. The professionals that are most readily available for their "low cost" and because usually research institutions "by mandate" encourage their employment, are young students and fellows. Irrespective of their quality, which is often very high, these people need to be trained and therefore for some time are more a hindrance than a help. The point is that the addition of people to a project requires an investment from the members of the project to integrate the new resources, and in time of crisis these resources may not be available to be mobilised. Quality. It can be very tempting to control a project via the quality of the code delivered. However writing low quality code is only marginally faster than writing good code. On the other hand, debugging low quality code can be much more time and resource consuming. Of course aiming at the highest possible quality (whatever this means) can also be a reason for failure. The definition of the "right" quality for a given code, and of the means of implementing it is one of the hardest tasks for a project manager, and we will come back to this point later on.
Scope. This is perhaps the least used parameter in software projects, and this is probably a legacy of the Software Engineering HCPs where the scope of the software is deeply embedded into the original planning. When properly employed, this is a very effective handle to control the evolution of a software project. Whenever a feature risks delaying a release, it should be seriously considered whether to re-schedule it for a subsequent release. In fact even anticipating a release when in a difficult situation could be a good decision, as this allows developers to focus on the really problematic items while reducing user pressure. The establishment of an a priori release schedule, irrespective of requirements and development times, has often been proposed as an effective way of managing a software project.
As we have seen above, the release strategy is central to the success of a software project. Most of the distinctive features of the HEP release process are common to modern Software Engineering and in particular to the Open Source community. Here, once again, we are faced with one more case of "independent discovery". Again, we can only regret that more selfconsciousness of our own procedures was not present, which could have led to a constructive dialogue with modern Software Engineering experts and Open Source project managers.

Testing and documentation
It is common knowledge that the importance of testing and documentation cannot be overemphasised in a software project. However both come at a price, and in a resource-strapped project these may well be in competition with the writing of the actual code and meeting the project deadlines. HEP software projects have developed specific strategies to cope with these problems.
Developing an exhaustive test suite represents a substantial amount of work, often comparable to the effort invested in writing the code itself. Moreover, the relation between the effort invested in a testing suite and the number of bugs that effectively "escape" it is not linear. While a relatively simple testing suite is invaluable at detecting a large percentage of the flaws of a new piece of code, the reward in terms of problems detected versus effort deployed in the improvement of the tests decreases rapidly.
In this HEP, the nimble release cycle effectively turns the user community into a large and exhaustive non-regression testing system. Given that the difference between releases is usually small, users can move quickly from one release to the next with their production code and therefore submit the newly released code to the most stringent test of them all, the full spectrum of real use cases. Of course this technique only works if some conditions are met.
The quality of the release must be indeed rather high. A new release that immediately breaks most user applications would simply block the development process. This means that there is a non-regression testing procedure that, however minimal, weeds out all the "trivial" bugs. Problems must be addressed quickly and professionally. The physics user community expects that programs may fail as a "fair" flip-side of seeing their requirements quickly addressed by the developers. However they also expect problems to be addressed quickly, either by workarounds or by the issue of a patched release. The code of the program must be easily available for inspection. This had often the positive effect that expert users may report not only the problem, but also a thorough diagnosis of its causes and, in several cases, a proposal for fixing it, if not the directly the corrected code! As a matter of fact, this can also help in writing the test suite itself. It is often the case that some (or all) of the code used to test the package comes directly from the users. Usually the code is chosen so that it provides exhaustive checks and can be run quickly. Because of the general Open Source policy of the user community, there is usually a large choice for this kind of code which makes very good test cases.
Documentation poses another problem, which is different in nature but not less serious. It is clear from what has been said that writing the documentation beforehand is not an option for a project where requirements, and hence features and functionality constantly evolve.
The lack of documentation of HEP codes is often taken as a fact, however a closer examination of the major programs shows that this is not necessarily the case. ROOT and so on all have extensive and well-written user manuals. Moreover the code of packages is usually rather well commented in-line. The fact is that this documentation is usually created only when the program reaches a certain maturity and therefore stability.

The people
The scientists participating in this project work for the different laboratories and universities which collaborate at the construction and exploitation of the detector. The important point to appreciate here is that the different groups are geographically spread in different institutes, countries and continents. Modern HEP experiments are composed of one or two thousand physicists coming from one hundred institutions located in tens of countries in different continents. The "project" relationship is rather informal, the different institutes being bound by a Memorandum of Understanding that cannot be legally enforced. An experimental collaboration itself has only a moral but not a legal status. The real link between the physicist participating to an experiment is the common goal of building and operating a detector for fundamental research.
In this situation the management of the Offline project has to proceed by consensus, and all decisions and agreements have essentially only a moral value. Not only most of the people participating to the Offline project from different institutes have no hierarchical relationship between them, but the project itself is defined and mandated by an entity (the experiment) that has no legal existence. This introduces a vast heterogeneity of relationships among individuals.

Why does it work at all?
We believe that HEP software development works out because there is a method behind it, well adapted to the environment. As we said the method is not formalised, and therefore it suffers from all the limitations of a tradition compared to a methodology. A traditional computer scientist may claim that there is no design. We maintain that design is done continuously, even if implicitly. The open discussion with all the users is the design activity that influences the evolution of the product. The new code is put into production very quickly: most of the time the users have direct access to the development repository. This in turn means that testing is continuous. The functionality of the product is defined, again implicitly but exhaustively, by the use made by the user community.
A common criticism is that the direction of the project is not clear. In reality the direction of the project is continuously redefined on the basis of the customer feedback: the project "goes where it needs to go", independently from, and most of the time beyond, what was decided at the beginning.
Critics claim that the code developed in this way is of low quality, difficult to maintain and to modify, not modular etc. The quality of the code developed in HEP varies largely. However most of the HEP products have served their purpose and a few products have been used by generations of experiments over tens of years and vastly changing technologies.
The downside of all this is the lack of formalisation of the process. Given the absence of a description and of manuals or other teaching materials on the software development practise, it takes time to train programmers in the HEP style of work, and people who do not have a natural inclination for it have bigger difficulties. The best developers are those who have a feeling for the needs of the user community, and there seems to be no way to learn or transmit this without finding an equally talented disciple.
A formalisation of this process would reduce these drawbacks. A clear, and possibly consensual, description of the best practises of HEP software development in the language and formalism of Software Engineering could help young researchers to become active more quickly and with less coaching. In spite of all evident advantages, this step has not been taken formally. We believe that this happened mainly because software developers in HEP were themselves unaware to be doing Software Engineering, and also because such an activity would have required an investment of resources, particularly from the main actors of these developments, and resources are notoriously in short supply in HEP software projects.

Modern software-engineering trends
It may now be instructive to give a quick overview of the modern Software Engineering trends to compare them with what has been said above about HEP software developments. As we have seen, HEP software developers are able to produce results under the following conditions: • Short time-to-market.
• Changing user community.
• Changing hardware and Operating System base.
These features have always been characteristic of HEP, but they are now also becoming commonplace in the Information Technology industry, particularly in the area of e-Business. These are the features that modern Software Engineering tries to capture and satisfy.
Modern Software Engineering is trying to respond to the relative inadequacy of classical methods and to the rapid evolution of software development conditions. The response to High Ceremony Processes are the so-called "Agile Methodologies" [10]. These methodologies tend to adapt to change rather than predict it, and they focus on people interaction rather than on process definition. The whole process is kept as simple as possible, in order to react quickly to change. This allows the introduction of an incremental and interactive development based on short iterations of the order of weeks, in constant dialogue with the customers and users. The work is steered by coding and testing rather than by analysis and design. These technologies are uncovering better ways of developing software by valuing: • Individual and interactions, more than processes and tools.
• Working software more than huge documentation.
• Customer collaboration more than contract negotiation. • Responding to change over following a plan. The value of the last items is not ignored, but the former are chosen every time there is a conflict. In analogy with High Ceremony Processes, agile technologies are also known as Low Ceremony Processes.
These new development methods, involving Low Ceremony processes, are becoming commonplace in modern Software Engineering.
One of the most successful, eXtreme Programming (XP) [11], has been recently described and represents one of the first Software Engineering methodologies that tries to reduce the cost of change, reducing initial design and centring the method on the process of change itself. XP is built around four simple principles: (i) Communication. A project needs continuous communication, with the customer and among developers. Design and code must be understandable and up to date. (ii) Simplicity. Do the simplest thing that can possibly work. Later, a simple design will be easily extended. (iii) Feedback. Take advantage of continuous feedback from customers on a working system, incrementally developed. Programming is test-based. (iv) Courage. The result of the other three values is that development can be aggressive. Every time a possible improvement in the system is detected, the system can be re-factored mercilessly.
XP is based on small, very interacting teams of people working in pairs. Testing is practised from the start, and every piece of code has its frequently run test suite. System integration is performed daily under continuous test. The development is use-case driven, with specific techniques to estimate time and cost of the project. Programs are continuously re-factored to follow the evolution of user requirements. Written documentation besides code is kept to a minimum until the program is released. The main achievement of XP is perhaps to have recast the traditional paradigm of Software Engineering (waterfall and spiral) into a much shorter timescale that is better adapted to present day software production in industry, which is very close to the normal practise in research.
Here again the similarities with HEP are very strong, even if the conditions in which XP has been developed are somewhat different from the environment of a typical HEP experiment. Evolving design, accent on most wanted features first, very short time-to-market, general availability of unreleased code for testing, i.e. constant Quality Assurance verification by the user community are all XP features that are commonplace in HEP development. There is however an important difference: HEP systems are built by distributed teams and not by small concentrated teams of programmers working in pairs as is prescribed by XP. However this needs not be a major obstacle. As with classical Software Engineering, agile methods are also models that need to be adapted to the specific software development situation. In this case the adaptation of agile technologies to HEP could give new insights into both fields.
It is very encouraging that modern Software Engineering trends seem to explain and justify what we have been doing for so many years, often feeling guilty about it. We finally start to understand why things worked in spite of the curses of generations of software pundits. This understanding, if properly exploited, may help us in doing things better, formalising and improving our process. Now that a new culture develops and agile methodologies begin to be recognised as a perfectly honourable way of working, we are feel some pride of having been precursors on this way, when the road was still full of obstacles.

Conclusions
HEP has developed and successfully deployed software for many years without using classical Software Engineering. Market conditions are now more similar to the HEP environment, and modern Software Engineering is confirming some HEP traditions and rituals that have proven successful even though they were never codified or otherwise justified. These developments may be important for HEP software as they may allow us to formalise our software development strategy. This could improve our planning capability for distributed software development and it may help to transmit and evolve our software practises, reducing the lead-time for developers to be productive in our field. This is particularly important now that it is difficult to find long-term positions in research, and most of the developments are due to young scientists who, after a stay in research, will look for further employment in the industry.
Our environment adds complexity to the one foreseen by agile methods, as we work in large and distributed teams, with little or no hierarchy. Therefore the challenge is now to move agile technologies into the realm of distributed development. The authors believe that this could be a worthy goal for Software Engineers working in HEP, and an occasion to collaborate more closely with advanced Computer Science and Industry.


extfieldsofstudy:
Physics
Computer Science
Mathematics

text:
Block synchronization for quantum information

Locating the boundaries of consecutive blocks of quantum information is a fundamental building block for advanced quantum computation and quantum communication systems. We develop a coding theoretic method for properly locating boundaries of quantum information without relying on external synchronization when block synchronization is lost. The method also protects qubits from decoherence in a manner similar to conventional quantum error-correcting codes, seamlessly achieving synchronization recovery and error correction. A family of quantum codes that are simultaneously synchronizable and error-correcting is given through this approach.

I. INTRODUCTION
The field of quantum information theory has experienced rapid and remarkable progress toward understanding and realizing large-scale quantum computation and quantum communication. One of the most important missions is to develop theoretical foundations for robust and reliable quantum information processing. The discovery of the fact that it is even possible for us to correct the effects of decoherence on quantum states was one of the most important landmarks in quantum information theory in this regard [1]. The field has since made various kinds of remarkable progress, from developing quantum analogues of important concepts in classical information theory to finding surprising phenomena that are uniquely quantum information theoretic [2]. Quantum error correction has been realized in various experiments as well [3][4][5][6][7][8][9][10][11].
One of the most important problems on reliable quantum information processing that remain unaddressed, however, is block synchronization (or, more commonly, "frame synchronization" in the language of classical communications [12]). In classical digital computation and communications, virtually all data have some kind of block structure, which means that in order for one to make sense of data, one must know the exact positions of the boundaries of each block of information, or word, in a stream of bits. This fact will stay the same in the quantum domain. In fact, not only will the actual quantum information one wishes to process most likely have a block structure for the same reason as in the classical domain, but procedures for manipulating quantum information also typically demand very precise alignment. For instance, we have a means to encode one qubit of information into five physical qubits to reduce the effects of decoherence to the theoretical limit [13]. However, this does not mean that we can apply the procedure to, say, the last three qubits * yuichiro.fujiwara@caltech.edu from an encoded quantum state and the first two qubits from the following information block to correct errors. If that worked, one would still not be able to correctly interpret the information carried by the qubits; after all, "quantum information theory" is not quite the same as "antumin formationth eory" with "qu" before it.
Block synchronization is critical when correct block alignment can not be provided or is difficult to provide by a simple external mechanism. For instance, block synchronization is a critical problem in virtually any area of classical digital communications, where two parties are physically distant, so that synchronization must be achieved through some special signaling procedure, such as inserting "marker" bits or using a specially allocated bit pattern as "preamble" to signal the start of each block (see, for example, [14,15] for the basics of block synchronization techniques for digital communications).
It is true that if we assume that a qubit always goes through wires as expected in a quantum circuit and that storing, retrieval, and transmission of quantum information are always securely synchronized by external physical mechanisms, then block synchronization is certainly not a problem. However, such a strict assumption imposes demanding requirements on hardware and limits what quantum information processing can offer. For example, without a software solution to block synchronization, quantum communication would have to always be supported by perfectly synchronized classical communications to a large degree [16].
One of the most substantial barriers to establishing block synchronization in the quantum domain is the fact that measuring qubits usually destroys the quantum information they contain. Existing classical block synchronization techniques typically require that the information receiver or processing device constantly monitor the data to pick up on inserted boundary signals, which translates into constant measurement of all qubits in the quantum case. Hence, if an analogue of a classical synchronization scheme such as inserting preamble were to be employed in a naive manner, one would have to know exactly where those inserted boundary signals are in order not to disturb quantum information contained in data blocks, which would require accurate synchronization to begin with.
One might then expect that a sophisticated block synchronization scheme based on information theory would be more attractive and promising in the quantum world. Another big hurdle lies exactly here; sophisticated coding for synchronization is already a notoriously difficult problem in classical information theory (see, however, [17] for a recent survey of coding theoretical approaches to fighting various kinds of synchronization error for the classical case). Making things more challenging, quantum bits are thought to be more vulnerable to environmental noise than classical bits, which implies that we ought to simultaneously answer the need for strong protection from the effects of decoherence.
The primary purpose of the present paper is to show that it is, indeed, possible to encode information about the boundaries of blocks into qubits in such a way that block synchronization recovery and quantum error correction are seamlessly integrated. The proposed scheme does not rely on external synchronization mechanisms or destroy quantum information by searching for boundaries. We make use of classical error-correcting codes with certain algebraic properties, so that the problem of finding such quantum synchronizable error-correcting codes is reduced to that of searching for special classical codes.
In the next section, we give a simple mathematical model of block synchronization in the quantum domain and define quantum synchronizable error-correcting codes. The details of our scheme is presented in Section III. Concluding remarks are given in Section IV.

II. BLOCK SYNCHRONIZATION
Here we give a simple mathematical model of block synchronization in the quantum setting. Note that while the term block might seem to suggest that each block is encoded by the same block code, we may treat them as more general structures, so that different blocks can contain different numbers of qubits encoded by different coding schemes.
Let Q = (q 0 , . . . , q x−1 ) be an ordered set of length x, where each element represents a qubit. A block F i is a set of consecutive elements of Q. Let F = {F 0 , . . . , F y−1 } be a set of blocks. The ordered set (Q, F ) is called a blockwise structured sequence if |{ i F i }| = x and F i ∩ F j = ∅ for i = j. In other words, the elements of a sequence are partitioned into groups of consecutive elements called blocks.
Take a set G = {q j , . . . , q j+g−1 } of g consecutive elements of Q. G is said to be misaligned by a qubits to the right with respect to (Q, F ) if there exits an integer a and a block F i such that F i = {q j−a , . . . , q j+g−a−1 } and G ∈ F . If a is negative, we may say that G is misaligned by |a| qubits to the left. G is properly aligned if G ∈ F .
To make this mathematical model clearer, take three qubits and encode each qubit into nine qubits by Shor's nine qubit code [1]. The resulting 27 qubits may be seen as Q = (q 0 , . . . , q 26 ), where the three encoded nine qubit blocks |ϕ 0 , |ϕ 1 , and |ϕ 2 form blocks F 0 = (q 0 , . . . , q 8 ), F 1 = (q 9 , . . . , q 17 ), and F 2 = (q 18 , . . . , q 26 ) respectively. These 27 qubits may be sent to a different place, stored in quantum memory or immediately processed for quantum computation. A device, knowing the size of each information block, operates on nine qubits at a time. If misalignment occurs by, say, two qubits to the left, the device that tries to correct errors on qubits in |ϕ 1 applies the error correction procedure to the set G of nine qubits q 7 , . . . , q 15 , two of which come from F 0 and seven of which F 1 . In this case, when measuring the stabilizer generator IZZIIIIII of the nine qubit code to obtain the syndrome, what the device actually does to the whole system can be expressed as which, if block synchronization were correct, would be I ⊗8 Z does not stabilize |ϕ 0 , nor does ZI ⊗8 |ϕ 1 . Hence, errors are introduced to the system, rather than detected or corrected. Similarly, if the same misalignment happens during fault-tolerant computation, the device that tries to apply logicalX to the third logical block |ϕ 2 will apply I ⊗16 X ⊗9 II to the 27 qubit system. Other kinds of synchronization error such as deletion may be considered in the quantum setting (see [17] for mathematical models of such errors in the classical case). As in the classical coding theory, however, we would like to separately treat them and do not consider fundamentally different types of synchronization in the current paper. Instead, we assume that no qubit loss or gain in the system occurs and that a device regains access to all the qubits in proper order in the system if misalignment is correctly detected.
Our objective is to ensure that the device identifies, without destroying quantum states, how many qubits off it is from the proper alignment should misalignment occur. A code that is designed for detecting this type of misalignment is called a synchronizable code in the modern information theory literature. Borrowing this term, we call a coding scheme a quantum synchronizable (a l , a r )-[[n, k]] code if it encodes k logical qubits into n physical qubits and corrects misalignment by up to a l qubits to the left and up to a r qubits to the right.
We assume that a linear combination of I, X, Z, and Y acts on each qubit independently over a noisy quantum channel. For error correction against such errors, we employ a version of syndrome decoding and show how to correct errors. In principle, the true values of the minimum distances of our quantum synchronizable codes can be computed. However, we focus on how many nontrivial quantum errors our decoding procedure can correct. Hence, the actual minimum distances of our quantum synchronizable codes may be larger than what our decoding algorithm suggests.
In what follows, we give a general construction for quantum synchronizable error-correcting codes and describe the procedures of encoding, error correction, synchronization recovery, and decoding. An infinite class of such quantum codes will be given at the end of the next section as an example.

III. CODING SCHEME
In this section we give the mathematical details of our solution and show how to realize quantum synchronizable codes. We employ classical and quantum coding theory. For the basic facts and notions in classical and quantum coding theories, the reader is referred to [2,18].

A. Preliminaries
As usual, we define a binary linear [n, k] code as a k-dimensional subspace of F n 2 , the n-dimensional vector space over the binary field. Because we do not consider a code over another field, we always assume that a classical code is binary unless otherwise stated.
A cyclic code C is a linear [n, k] code with the property that if c = (c 0 , . . . , c n−1 ) is a codeword of C, then so is every cyclic shift of c. It is known that, by regarding each codeword as the coefficient vector of a polynomial in F 2 [x], a cyclic code can be seen as a principal ideal in the ring F 2 [x]/(x n − 1) generated by the unique monic nonzero polynomial g(x) of minimum degree in the code which divides x n − 1. Computations in F 2 [x]/(x n − 1) are modulo x n − 1. A cyclic shift thus corresponds to multiplying by x, and the code can be written as C = {i(x)g(x) | deg(i(x)) < k}. Multiplying by x is an automorphism. The orbit of a given codeword i(x)g(x) by this group action is written as Let C and D be two linear codes of the same length. 2 ⌋ quantum errors can be corrected through a separate twostep error correction procedure by directly exploiting the error correction mechanism of the corresponding classical code. A higher quantum error correction capability may be achieved if the code is degenerate. For the sake of simplicity, however, we do not investigate the degeneracy of each individual quantum error-correcting code. In the remainder of this paper, we assume familiarity with the structure of CSS codes as well as their basic encoding and decoding mechanisms given in a standard textbook such as [2].

B. Main theorem
Our main theorem employs a pair of cyclic codes C and D satisfying C ⊥ ⊆ C ⊂ D to generate a quantum synchronizable code.
Theorem 1 If there exist a dual-containing cyclic [n, k 1 , d 1 ] code C and a C-containing cyclic [n, k 2 , d 2 ] code with k 1 < k 2 , then for any pair of nonnegative integers a l , a r satisfying a l + a r < k 2 − k 1 there exists a quantum synchronizable (a l , a r )-[[n + a l + a r , 2k 1 − n]] code that corrects at least up to ⌊ d1−1 2 ⌋ phase errors and at least up to ⌊ d2−1 2 ⌋ bit errors. To prove Theorem 1, we realize a quantum synchronizable code as a carefully translated vector space similar to a CSS code. The proof of the above theorem will be completed in Section III D 5 after describing encoding and decoding procedures in Section III C and Sections III D 1-4.
Let C be a dual-containing cyclic [n, k 1 , d 1 ] code that lies in another cyclic [n, k 2 , d 2 ] code D with k 1 < k 2 . Define g(x) as the the generator of D = g(x) which is the unique monic nonzero polynomial of minimum degree in D. Define also h(x) as the generator of C which is the unique monic nonzero polynomial of minimum degree in C. Since C ⊂ D, the generator g(x) divides every codeword of C. Hence, h(x) can be written as h(x) = f (x)g(x) for some polynomial f (x) of degree n − k 1 − deg(g(x)) = k 2 − k 1 .
For every polynomial j(x) = j 0 +j 1 x+· · ·+j n−1 x n−1 of degree less than n, define |j(x) as the n qubit quantum state |j(x) = |j 0 |j 1 · · · |j n−1 . For a set J of polynomials of degree less than n, we define |J as Because R is a system of representatives, these 2 2k1−n states form an orthonormal basis. Let V g be the vector space of dimension 2 2k1−n spanned by V g . We employ this translated space V g to prove Theorem 1.

C. Encoding
Take a full-rank parity-check matrix H D of D. For each row of H D , replace zeros with Is and ones with Xs.
Perform the same replacement with Is for zeros and Zs for ones. Because C ⊥ ⊂ C ⊂ D implies D ⊥ ⊂ D, the code D is a dual-containing cyclic code of dimension k 2 . Hence, the resulting 2(n−k 2 ) Pauli operators on n qubits form stabilizer generators S D of the Pauli group on n qubits that fixes a subspace of dimension 2 k2 . The set of the Pauli operators on n qubits in S D that consist of only Zs and Is is referred to as S Z D . Construct stabilizer generators S C in the same manner by using C.
Take an arbitrary 2k 1 − n qubit state |ϕ , which is to be encoded. By using an encoder for the CSS code of parameters [[n, 2k 1 −n]] defined by S C , the state |ϕ is encoded into n qubit state |ϕ enc = i α i |v i , where each v i is an n-dimensional vector with the orthogonal basis being C ⊥ + r i (x) | r i (x) ∈ R . Let U g be the unitary operator that adds the coefficient vector g of g(x). By applying U g , we have: Take a pair of nonnegative integers a l , a r that satisfy a l + a r < k 2 − k 1 . Using a l + a r ancilla qubits and CNOT gates, we take this state to an n + a l + a r qubit state as follows: where w 1 i and w 2 i are the last a l and the first a r portions of the vector v i + g respectively. The resulting state |ψ enc = i α i w 1 i , v i + g, w 2 i then goes through a noisy quantum channel.

D. Error correction and block synchronization
Gather n + a l + a r consecutive qubits G = (q 0 , . . . , q n+a l +ar −1 ). We assume the situation where correct block synchronization means that G is exactly the qubits of |ψ enc , but G can be misaligned by a qubits to the right, where −a l ≤ a ≤ a r .
Let P = (p 0 , . . . , p n+a l +ar −1 ) be the n + a l + a r qubits of the encoded state. If a = 0, then P = G. Define G m = (q a l , . . . , q a l +n−1 ). By assumption, G m = (p a l +a , . . . , p a l +n−1+a ). Let n-fold tensor product E of linear combinations of the Pauli matrices be the errors that occurred on P .
We first outline the bit error correction procedure on the window G m . Synchronization is recovered after making G m free from bit errors. The bit errors outside of G m are then corrected. The phase errors on qubits will be treated at the final step after reversing the extension process.

Bit error correction on the initial window
We correct bit errors that occurred on qubits in G m in the same manner as the separate two-step error cor-rection procedure for a CSS code. Since C ⊂ D, the vector space spanned by the orthogonal basis stabilized by S D contains V g as a subspace. Hence, through a unitary transformation using S Z D , we can obtain the error syndrome in the same manner as when detecting errors with the CSS code defined by S D as follows: where |χ is the n − k 2 qubit syndrome by S Z D . If E introduced at most ⌊ d2−1 2 ⌋ bit errors on qubits in G m , these quantum errors are detected and then corrected by applying the X operators if necessary.
More formally, rewrite the original encoded state where c i correspond to the window misaligned by a qubits to the right, which can be obtained by cyclically shifting v i + g. Hence, the binary vectors l i , and r i are of lengths a l + a and a r − a respectively. Without loss of generality, we consider E the discretized bit errors and phase errors on the n + a l + a r qubits of |ψ enc . Let e b be the (n + a l + a r )-dimensional binary error vector such that i ∈ supp(e b ) if and only if a bit error occurred on qubit p i . In other words, the positions of 1s in e b represent which qubits are bitwise flipped. Define the phase error vector e p in the same way for the phase errors that occurred on |ψ enc . Then, the transformation due to the noisy quantum channel that introduced quantum error E is Write the bit error vector as e b = (e b l , e b c , e b r ), where e b l , e b c , and e b r are the first a l + a, next n, and last a r − a bits of e b respectively. Recall that H D is the full-rank parity-check matrix of D corresponding to the stabilizer generators. We perform the following unitary transformation using S Z D with n − k 2 ancilla qubits: Because H D is a parity-check matrix of D, measuring the ancilla gives the error syndrome in the same manner as the corresponding classical linear code does. Thus, as in the standard bit error correction procedure for a CSS code, if we assume that E introduced at most ⌊ d2−1 2 ⌋ bit errors on qubits in G m , applying X operators to qubits specified by the error syndrome H D e b c takes the encoded sate with errors to where E ′ represents the partially corrected quantum errors.

Synchronization recovery
We perform synchronization recovery by exploiting the bit-error-free G m we just obtained. Recall that all codewords of C ⊥ and r i (x) ∈ R belong to C, and hence to D as well. Because g(x) is the generator of D, it divides any polynomial of the form s(x) + r i (x) + g(x) over for some polynomials i 0 (x) and i 1 (x) of degree less than k 1 , the quotient is of the form j(x)f (x) + 1 for some polynomial j(x). Dividing the quotient by f (x) gives 1 as the remainder. Note that g(x) is a monic polynomial of degree n − k 2 that divides x n − 1, where k 2 is strictly larger than ⌈ n 2 ⌉. Let i be an integer satisfying 1 ≤ i ≤ ⌈ n 2 ⌉ ≤ k 2 − 1. Then ).
Hence, we have |Orb(g(x))| ≥ k 2 > ⌈ n 2 ⌉. Because |Orb(g(x))| must divide n, we have |Orb(g(x))| = n. Thus, applying the same two-step division procedure to any polynomial appearing as a state in cyclically shifted V g by a qubits gives x a (mod f (x)) as the remainder. By assumption, we have and −a l ≤ a ≤ a r . Thus, the remainder x a (mod f (x)) is unique to each possible value of a.
Recall that every state in V g is of the form C ⊥ + r i (x) + g(x) . Because G m contains no bit errors, the basis states of the corresponding portion in E ′ |ψ enc are the cyclically shifted coefficient vectors of the correct polynomials. Let Dq t(x) and Dr t(x) be the polynomial division operations on n qubits that give the quotient and remainder respectively through quantum shift registers defined by a polynomial t(x) of degree less than n [21] (see also [22] for an alternative way to implement quantum shift registers). Let Q = I ⊗a l +a Dq g(x) I ⊗ar−a and R = I ⊗n+a l +ar Dr f (x) , so that the two represent applying Dq g(x) to the window and Dr f (x) to the ancilla qubits of Dq g(x) that contain the calculated quotient. These operations give the syndrome for the synchronization error as for the CSS code based on the dual-containing cyclic code C: → E ′′′ |ϕ enc |H C (e p c + (0, e p l ) + (e p r , 0)) , where H C is a full-rank parity-check matrix of C and E ′′′ is the phase error operator on |ϕ enc that represents the effect of e p c + (0, e p l ) + (e p r , 0). Applying Z operators on the qubits specified by the syndrome completes the error correction procedure.

Proof of Theorem 1 and example codes
We are now able to prove Theorem 1. Proof of Theorem 1. Take a dual-containing cyclic [n, k 1 , d 1 ] code C that is contained in a cyclic [n, k 2 , d 2 ] code, where k 1 < k 2 . Encode 2k 1 − n logical qubits into n + a l + a r physical qubits as described above. The error correction and synchronization recovery procedures described above correct misalignment by a qubits to the right as long as a lies in the range −a l ≤ a ≤ a r and correct up to ⌊ d1−1 2 ⌋ phase errors on the n + a l + a r qubits and up to ⌊ d2−1 2 ⌋ bit errors on any consecutive n qubits. The final decoding step is completed by reducing the state |ϕ enc = i α i |v i to the original state |ϕ by a decoding circuit of the CSS code based on the dualcontaining cyclic code C. Thus, the scheme is a quantum synchronizable (a l , a r )-[[n + a l + a r , 2k 1 − n]] code with the desired error correction capability.
To take full advantage of Theorem 1, we need dualcontaining cyclic codes that achieve large minimum distance and contain dual-containing cyclic codes of smaller dimension. A class of the well-known Bose-Chaudhuri-Hocquenghem (BCH) codes [18] gives such classical codes. The dual-containing properties of BCH codes have been thoroughly investigated in [23,24]. The following is an infinite series of quantum synchronizable errorcorrecting codes based on a class of such codes, called the primitive, narrow-sense BCH codes (see [18] for the definition and basic properties of primitive, narrow-sense BCH codes): Corollary 2 Let n, d 1 , and d 2 be odd integers satisfying and any pair of nonnegative integers a l , a r satisfying a l + a r < m(d1−d2) 2 there exists a quantum synchronizable (a l , a r )-[[n + a l + a r , n − m(d 2 − 1)]] code that corrects up to phase errors on the n + a l + a r qubits and up to bit errors on any consecutive n qubits.
Proof. Let n, d 1 , and d 2 be integers satisfying the condition given in the statement. Let D be a primitive narrow-sense BCH code of length n and designed distance d 2 such that 3 ≤ d 2 < 2 ⌈ m 2 ⌉ − 1. Construct a primitive narrow-sense BCH code C by joining one or more cyclotomic cosets, so that its designed distance d 1 is larger than d 2 but smaller than or equal to 2 ⌈ m 2 ⌉ − 1. The dimensions of C and D are n − m(d1−1) 2 and n − m(d2−1) 2 respectively. D contains C, and the two cyclic codes are both dual-containing (see [23]), forming the desired quantum synchronizable codes.

IV. CONCLUSION
We developed a coding scheme that seamlessly integrates block synchronization and quantum error correction. A close relation is found between quantum synchronizable error-correcting codes and pairs of cyclic codes with special properties. Through this relation, the well-known BCH codes were shown to generate desirable quantum codes for block synchronization.
In classical communications, a unified method for synchronization and error correction can reduce implementation complexity [25]. A similar method using cyclic codes has also been proposed recently in the classical domain for simple implementation of asynchronous code division multiple access (CDMA) systems with random delays [26]. We hope that our seamlessly unified solution to block synchronization and quantum error correction may help simplify requirements on hardware and open up new possibilities of quantum computation and quantum communication such as transmission of a large amount of consecutive quantum information blocks with little aid from classical communications.
One potential weakness of the approach presented in this paper is that our quantum synchronizable codes of length n + a l + a r may face a larger number of quantum errors than the underlying standard CSS codes of length n would because of their extended lengths. For instance, in a scenario where the receiver missed the first several qubits, the window may be suffering from severe quantum errors which may not be correctable. Phase error correction requires particular attention in this regard because while the current scheme takes advantage of the subcode C, which typically has a larger minimum distance than D for bit errors, the error correction scheme for phase errors is expected to handle all phase errors at once unlike the bit error correction procedure. While the ability to recover from misalignment is highly valuable because even the slightest synchronization error is fatal to information transmission, these weaknesses should be noted and are worthy of further investigation. One aspect we may be able to improve is the maximum magnitude of a correctable synchronization error. The scheme presented in this paper relies on the uniqueness of the syndrome for each possible combination of the magnitude and direction. While the remainder x a (mod f (x)) after the two-step division procedure for synchronization recovery is certainly unique if we limit a l +a r to be less than deg(f (x)), this may be overly conservative in a sense. In fact, there are 2 deg(f (x)) possible polynomials of degree deg(f (x)) or smaller while we only need at most n distinct synchronization error syndromes even if we extend a CSS code of length n to a full 2n qubit code by copying all n qubits with CNOT gates. While our scheme does not appear to allow a better general bound on the maximum correctable magnitude in a simple form without a deeper observation and careful modification, it is plausible that a sophisticate treatment of syndromes may yield quantum synchronizable codes with better synchronization error tolerance than is proved in this paper.
Finally, while we have focused on binary dualcontaining cyclic codes, it is certainly of interest to look into more general approaches to quantum error correction such as orthogonal pairs of cyclic codes that are not dual-containing and the quantum error-correcting codes from additive codes over F 4 found in [27]. While CSS codes and similar quantum error-correcting codes based on classical cyclic codes that admit decoding through quantum shift registers have not been studied very well in the literature, there are some examples that have very similar structures such as quantum Reed-Solomon codes [28] (see also [21] for a possible decoding scheme for this type of quantum error-correcting code through quantum shift registers). A further look into these types of quantum cyclic code would be of interest.


Simulation of a Broadcasting Method Based on Busy Tone

When the receiving nodes are uncertain or the topology of the ad hoc network is high dynamic, broadcasting is an effective data dissemination method. In this research, a broadcasting method based on busy tone is modeled and implemented with the network simulation platform OPNET, and the performance of the broadcasting method is analyzed based on experimental results. Experimental results show that, in the network with various load, performance of the broadcasting method based on busy tone is good.

Introduction
When the receiving nodes are uncertain or the topology of the ad hoc network is high dynamic, broadcasting is an efficient technique to exchange information. In this paper, the broadcasting method based on busy tone is modeled and implemented with OPNET network simulation platform, and its performance is analyzed.

A broadcasting method based on busy tone
Currently, the most widely used channel reservation mechanism is RTS/CTS handshake. For example, in BSMA protocol, BWM protocol, BMMM protocol, LAMM protocol etc [1][2][3][4][5][6][7] , RTS/CTS handshake is used to reserve channel. The cost of RTS/CTS handshake is increased network load of transmitting a lot of control packets.
The assumption of RTS/CTS mechanism is that all the related nodes can receive RTS/CTS control package. But this assumption is not always true for the mobile ad hoc network in which the relative position of nodes changes rapidly. RTS/CTS handshake has following disadvantages: (1) Due to the rapid changing relative position of nodes, a complete handshake between source node and destination node is difficult to completed, which lead to unexpected access channel delay.
(2) RTS/CTS handshake not only notifies the nodes in one-hop range of source node with RTS, but also notifies the nodes in two hops range of source node with CTS the coming broadcasting. Therefore, RTS/CTS handshake reserves two hops range channel of source node. In the high density network, reserve two hops would lead to a large number of nodes waiting to access the common channel.
In a word, reserve channel with RTS/CTS handshake is complex and the access channel delay is long in high density network.
To overcome the problems caused by RTS/CTS handshake, referring to some unicast methods, this research designed a single-hop broadcasting method based on busy tone. In this method, busy tone is used to reserve the one hop channel of source node, the broadcasted data message is used to indicate the one hop channel state of source node.
In the single-hop broadcasting method based on busy tone, transmitter and receiver both have two channels: the channel transmits data message is called data channel, and the other channel transmits busy tone is called busy tone channel.
Following is the operation process of the single-hop broadcasting method: (1) Node detects data channel and busy tone channel through receiver: 1) If data channel is busy, then receive data message. Receive data message over, continue to detect data channel and busy channel.
2) If busy tone channel is busy and data channel is free, which means that there is other node in one hop range is reserving channel, continue to detect data and busy tone channel.
3) If data channel is free, busy tone channel is free, and the node itself has data to broadcast, then start to reserve channel. 4) If data channel is free, busy tone channel is free, and the node itself has no data to broadcast, then continue to detect data and busy tone channel.
(2) The process of reserve channel is: Set Timer t, t=d/c, where d is the one hop range of wireless signal, c is the propagation velocity of wireless signal, and t is the time span of wireless signal propagate one hop range. Broadcast busy tone, detect data and busy tone channels: 1) If data channel is busy before time t out, then stop broadcasting busy tone, and start to receive data message.
2) If data channel is free, and there's busy tone from other node before time t out, then cancel Timer, stop broadcasting busy tone, back off for a time span t', and continue to detect channel.
3) If data and busy tone channels are free before time t out, then the node reserves channel successfully. The node starts to broadcast data. When broadcasting data message is over, continue to detect data and busy tone channel.

Modeling and implementation of the broadcasting method based on busy tone with OPNET platform
OPNET is one of the most widely used network simulation platform. Modeling with OPNET consists three parts: network modeling, node modeling and process modeling. Network model describes network topology, geographical layout, and mobility, etc. Node model describes various kinds of calculation and communication devices in the network. Process model describes the communication operation of node, such as protocol, algorithm, etc. In a word, the main task of network simulation is to design network model, node model, and process model. The design and implement of broadcasting method is to design corresponding node model and process model. Node model design. Node model is to describe node's function. A node is usually made up of many modules and each module plays one part of the node function, such as data generation and storage, etc. To simulate the broadcasting method, in this research, the node model comprises six modules as shown in figure 1. (2) Module rt_0 is a wireless transmitter, and rr_0 is a wireless receiver. The wireless transmitter and receiver have two channels: data channel and busy tone channel.

1136
Information Technology for Manufacturing Systems III (3) Module a_0 is an antenna.
(4) Module data_pro is the module to implement the broadcasting method. Following is the functions of the module: 1) Receive the data from module gen, and choose proper time to transmit it to the data channel of rt_0.
2) Reserve channel with busy tone.
3) Receive data from rr_0. 4) Detect data channel and busy tone channel by rr_0. 5) Detect data channel by rt_0. (5) Sink is the module to destroy the busy tone packet received from rr_0. Simulation of busy tone. In OPNET, packet transmission is used to simulate information flow in practical network. Theoretically, busy tone is analog signal looking like sine wave. To design simulation model of the broadcasting method based on busy tone with OPNET platform, it is critical to simulate busy tone with packet transmission. To stop busy tone transmission and free channel on time, small packet is used to simulate busy tone. Here, suppose busy tone channel data rate of transmitter and receiver is set as 10 6 bps, busy tone packet length is 1 bit. To simulate continuous busy tone signal, the interval time to generate and send busy tone packet is 10 -6 seconds. Process design. Each module in node model is implemented by a process model. Following we design data_pro module, which implements the broadcasting method based on busy tone. With OPNET, algorithm is described as state transition machine. To develop state transition machine, following steps are carried out: (1) Abstract the states of the protocol process, making sure that these states are mutually exclusive and complementary. The process can only be at one state at one time.
(2) Determine the possible event in the process, construct events response table, and final establish state transition machine.
Abstract states and events of the process. State is a module of a process. States are mutually exclusive and complementary. Process should be at only one state at one time, and all states make up of the process state space. During simulating, the process keeps transiting from one state to another. Based on the operation principle, process of the broadcasting method based on busy tone includes six states, which are listed in table 1. Event is the motivation to state transition. Each event is an interrupt and has an interruption type. According the operation process of the method, events of the process are listed in table 2. Establish state transition machine. According to the broadcasting method operation process, process states, process interrupts, state transition machine could be established, which is shown in figure 2. In figure 2, red state is unforced and green state is forced. Unforced state can stop the process running, while forced state can not stop the process running. Interrupts motivate the process transit from one unforced state to another unforced state. The initial unforced state is IDLE.  To validate the performance of the broadcasting method in the network with various load, a series of scenarios are designed. In all the scenarios, network range is 1200m×50m, distance of one hop Information Technology for Manufacturing Systems III is 600m， data packet length is 100bit， date rate of transmitter and receivers is 10 6 bps， interval time of node generate data packet is 1 packet per second. Nodes number of scenario 12, 13 and 14 are 40, 120, 240 respectively.
Experimental results are shown in figure 3 and table 3. As shown in figure 3 and table 3, in network with various of network load, the end-to-end delay of the single-hop broadcasting method is stable and almost the same. The end-to-end delay is about 10 -4 second, and most of the one hop range nodes could receive the broadcasted data.

Conclusion
In this paper, with OPNET network simulator, a single-hop broadcasting method based on busy tone is modeled and implemented. Experimental results show that in the various load network, performance of this broadcasting method is good.


Parsing TCT with a Coarse-to-fine Approach

A key observation is that concept compound constituent labels are detrimental to parsing performance. We use a PCFG parsing algorithm that uses a multilevel coarse-to-fine scheme. Our approach requires a sequence of nested partitions or equivalence classes of the PCFG nonterminals, where the nonterminals of each PCFG are clusters of nonterminals of the finer PCFG. We use the results of parsing at a coarser level to prune the next finer level. The coarse-to-fine method use hierarchical projections for incremental pruning. We present experiments which show that parsing with hierarchical state-splitting is fast and accurate on Tsinghua Chinese Treebank. In addition, we propose a multiple-model method that adds concept compound labels to the output of the simple PCFG model and gains higher bracketing recall from the simple model. This scheme can be implemented by training two models on different labeling styles.

Introduction
The peculiarity of the annotation of this released edition of TCT is that the tree structure is very compact, where there are no unary productions except root nodes and leaf nodes.
A major observation is that parser on treebank with concept compound constituent labels performs worse than without concept compound constituent. The average crossing is 4% lower in presence of concept compound constituent labels.
Since all phrases have a clausal and phrasal constituent label, while only a fraction have concept compound constituent label. We can regard a phrase label with both clausal and phrasal constituent label and concept compound constituent label as a subsymbol of the clausal and phrasal constituent label merely.
The coarse categories in these grammars can be regarded as clusters or equivalence classes of the fine nonterminal categories. We require that the partition of the nonterminals defined by the equivalence classes at finer level be a refinement of the partition defined at coarser level. This means that each nonterminal category at finer level is mapped to a unique nonterminal category at coarser level (although in general the mapping is many to one, i.e., each nonterminal category at coarser level corresponds to several nonterminal categories at finer level). We use the correspondence between categories at different levels to prune possible constituents. A constituent is considered at finer level only if the corresponding constituent at coarser level has a probability exceeding some threshold. Parsing with hierarchical grammar leads to considerable efficiency improvements.
Treebank parsing comprises two problems: learning, in which we must select a model given a treebank, and inference, in which we must select a parse for a sentence given the learned model. Previous work has shown that highquality unlexicalized PCFGs can be learned from a treebank, either by manual annotation (Klein and Manning, 2003) or automatic state splitting (Matsuzaki et al., 2005;Petrov et al., 2006). In particular, we demonstrated in Petrov et al. (2006) that a hierarchically split PCFG could exceed the accuracy of lexicalized PCFGs (Collins, 1999;Charniak and Johnson, 2005). We adopted here a multilevel coarse-to-fine PCFG parsing algorithm as in  and Petrov (2007). The multilevel coarse-to-fine PCFG parsing algorithm reduces the complexity of the search involved in finding the best parse and attempts to constrain the fine parsing space to the coarse parsing space. It defines a sequence of increasingly more complex PCFGs.  has demonstrated that coarse PCFG identified the locations of correct constituents of the parse tree (the "gold constituents") with high recall.

Experiment Observation
We have parsed with three different annotation setups. First, we train our model our model with only phrasal labels, and evaluate the precision and recall on only the phrasal labels. Second, we train our model with full labels, and evaluate the precision and recall on only the phrasal labels. Third，we train the model with full labels, and evaluate the precision and recall on full labels.
The parsing performances metrics convinced that the concept compound is detrimental to the parser performance even we only evaluate the phrasal constituent labels' precision and recall.
Furthermore, we compare the metrics of exact match, average crossing, no crossing and 2 or less crossing, which show that the higher accuracy gained by stripping the concept compound labels lies in both its more accurate bracketing and tagging ability.

Previous Researches
Coarse-to-fine search is an idea that has appeared several times in the literature of computational linguistics and related areas. Maxwell and Kaplan (1993) extracted CFG automatically from a more detailed unification grammar and used it to identify the possible locations of constituents in the more detailed parses of the sentence. They use their covering CFG to prune the search of their unification grammar parser in essentially the same manner as we do here, and demonstrate significant performance improvements by using their coarse-to-fine approach.
Geman and Kochanek (2001) laid out the basic theory of coarse-to-fine approximations and dynamic programming in a stochastic framework. They describes the multilevel dynamic programming algorithm needed for coarse-to-fine analysis (which they apply to decoding rather than parsing), and show how to perform exact coarse-to-fine computation, rather than the heuristic search we perform here. Goodman (1997)'s parser is a two-stage coarse to fine parser. The second stage is a standard tree-bank parser while the first stage is a regular-expression approximation of the gram-mar. Again, the second stage is constrained by the parses found in the first stage. Neither stage is smoothed.
The parser of Charniak (2000) is also a twostage coarse to fine model, where the first stage is a smoothed Markov grammar (it uses up to three previous constituents as context), and the second stage is a lexicalized Markov grammar with extra annotations about parents and grandparents. The second stage explores all of the constituents not pruned out after the first stage. Related approaches are used in Hall (2004) and Charniak and Johnson (2005). Klein and Manning (2003a) describe efficient A* for the most likely parse, where pruning is accomplished by using Equation 1 and a true upper bound on the outside probability. While their maximum is a looser estimate of the outside probability, it is an admissible heuristic and together with an A* search is guaranteed to find the best parse first. One question is if the guarantee is worth the extra search required by the looser estimate of the true outside probability.
Tsuruoka and Tsujii (2004) explore the framework developed in Klein and Manning (2003a), and seek ways to minimize the time required by the heap manipulations necessary in this scheme. They describe an iterative deepening algorithm that does not require a heap. They also speed computation by precomputing more accurate upper bounds on the outside probabilities of various kinds of constituents. They are able to reduce by half the number of constituents required to find the best parse (compared to CKY). McDonald et al. (2005) have implemented a dependency parser with good accuracy (it is almost as good at dependency parsing as Charniak (2000)) and very impressive speed (it is about ten times faster than Collins (1997) and four times faster than Charniak (2000)). It achieves its speed in part because dependency parsing has a much lower grammar constant than does standard PCFG parsingafter all, there are no phrasal constituents to consider. The current paper can be thought of as a way to take the sting out of the grammar constant for PCFGs by parsing first with very few phrasal constituents and adding them only after most constituents have been pruned away.

Hierarchically Split PCFGs
We use a novel coarse-to-fine processing scheme for hierarchically split PCFGs. Our method con-siders the splitting history of the final grammar, projecting it onto its increasingly refined prior stages. For any projection of a grammar, we use techniques for infinite tree distributions (Corazza and Satta, 2006) and iterated fix point equations. We then parse with each refinement, in sequence, much along the lines of .
We consider PCFG grammars in a hierarchy fashion in Petrov et al. (2006). From the starting point of the raw treebank grammar, we iteratively refine the grammar in stages. The refined grammar is estimated using a variant of the forward-backward algorithm (Matsuzaki et al., 2005). After a splitting stage, many splits are rolled back based on (an approximation to) their likelihood gain. This procedure gives an ontogeny of grammars from the raw grammar to the final grammar. Empirically, the gains on the English Penn treebank level off after 6 rounds.

Coarse-to-Fine Search
When working with large grammars, it is standard to prune the search space in some way. In the case of lexicalized grammars, the unpruned chart often will not even fit in memory for long sentences. Several proven techniques exist. Collins (1999) combines a punctuation rule which eliminates many spans entirely, and then uses spansynchronous beams to prune in a bottom-up fashion. Charniak et al. (1998) introduces best-first parsing, in which a figure-of merit prioritizes agenda processing. Most relevant to our work is Charniak and Johnson (2005) which uses a preparse phase to rapidly parse with a very coarse, unlexicalized treebank grammar. Any item with sufficiently low posterior probability in the preparse triggers the pruning of its lexical variants in a subsequent full parse.  introduces multi-level coarse-to-fine parsing, which extends the basic pre-parsing idea by adding more rounds of pruning. In their work, the extra pruning was with grammars even coarser than the raw treebank grammar, such as a grammar in which all nonterminals are collapsed. We propose a novel multi-stage coarse-to-fine method which is particularly natural for our hierarchically split grammar, but which is, in principle, applicable to any grammar. Petrov et al. (2007) construct a sequence of increasingly refined grammars, reparsing with each refinement. They derive sequences of refinements and automatically tune the pruning thresholds on held-out data. Their hierarchical coarse-to-fine parsing take the projection that collapses split symbols in finer round to their earlier identities in coarser round. The final statesplit grammars G come, by their construction process, with an ontogeny of grammars where each grammar is a (partial) splitting of the preceding one.

Experimental Setup
We ran experiments on TCT. The training and test data set splits are described in Table below

Final Results
We took the final model and used it to parse the specified test set in the 3nd Chinese Parsing Evaluation which contains 1000 sentences, and achieved the best precision, recall and F-measure. We use the evaluation method released by CLP 2012.

Another Relabeling Method
A major observation is that concept compound constituent labels are detrimental to parsing performance. Since clausal and phrasal constituent labels are obligatory, while concept compound constituent labels are optional, we can strip concept compound constituent labels and parse with only clausal and phrasal constituent labels. Experiments show that parsing performance without concept compound constituents labels, especially the bracketing precision is significantly superior to the one with concept compound constituents labels.
Therefore, parsing directly with full labels (both clausal and phrasal constituent labels and concept compound labels) is unwise. In this paper, we get the concept compound label by the parser with full label, but get the extra performance gain by the parser with only clausal and phrasal constituent labels.

Integration of Both Parser
Clausal and phrasal constituent labels distinguish constituent phrasal categories, and full label (phrasal constituent label together with compound constituent label) moves forward to distinguish constituent structures.
A parser trained on the trees with only phrasal constituent labels have higher bracketing accuracy and phrasal constituent labels tagging accuracy. While another step can label the decoded tree with concept compound tags, either by incorporating the concept compound labels from the output of a parser trained on full label, or by relabeling the concept compound labels with a maximum entropy model.
In order to get strength from the both the parser output with and without concept compound labels, we train parser on both trees with only phrasal constituents label and full label, then add the concept compound labels from the later parser to the phrasal constituent labels from the former parser.
The simple PCFG identified the locations of correct constituents of the parse tree (the "gold constituents") with high precision and recall. Then we label the concept compound labels in corresponds to the complex PCFG.

Conclusion
We employ a novel parsing algorithm based upon the coarse-to-fine processing model. It takes the unpruned constituents and specifying them in the next level of granularity.
The coarse-to-fine scheme allows fast, accurate parsing. For training, one needs only a raw context-free treebank, and for decoding one needs only a final grammar, along with coarsening maps.
In addition, we propose a delicate integration method based upon two independently trained parsing models with different tree annotation style. The final output gains the higher bracketing label precision and recall from simpler tree annotation style, and adding the concept compound labels form the more complex tree annotation model.