Study of the Impact of PHY and MAC Parameters in 3GPP C-V2V Mode 4

In the latest years, 3GPP has added short range cellular-vehicle-to-anything (C-V2X) to the features of LTE and 5G in order to make vehicles, roadside devices, and vulnerable users directly exchange information using the same chipset as for classical long range connections. C-V2X is based on the use of advanced physical layer techniques and orthogonal resources, and one of the main aspects affecting its performance is the way resources are allocated. Allocations can be either managed by the network or in a distributed way, directly by the nodes. The latter case, called Mode 4, is defined to manage those situations where the network cannot be involved in the scheduling process, for example due to a lack of coverage, but could also be adopted in order to reduce the processing burden of eNodeB. An algorithm, defined in the standards, makes nodes sense the medium and identify the best time-frequency combination to allocate their messages. Focusing on C-V2V Mode 4, in this work we analyze the parameters of the algorithm designed by 3GPP and their impact on the system performance. Through simulations in different large scale scenarios, we show that modifying some parameters have negligible effect, that the proper choice of others can indeed improve the quality of service, and that a group of parameters allows to trade-off reliability with update delay. The provided results can also be exploited to guide future work.

I. INTRODUCTION
Everyone is agreed that cooperative and automated vehicles (CAVs) are coming on our roads in the next few years, completely changing the way mobility is conceived today. As often remarked, full automation is not enough and wireless technologies will play a key role.
In this scenario, as an alternative to the well known and widely tested IEEE 802.11p (and related standards), 3GPP has added new dedicated features to the cellular ecosystem to enable short range communications in the so-called cellularvehicle-to-anything (C-V2X). More specifically, by the end of 2016, advanced features have been added in Release 14 to enable direct device-to-device (D2D) communications for the specific scenario of vehicular networks [1]. Such technology will enable short-range vehicle-to-vehicle (V2V), vehicle-to-infrastructure (V2I), and vehicle-to-pedestrian (V2P) communications, integrated with classical long-range coverage.
Distinctive characteristics of short-range C-V2X with respect to IEEE 802.11p are its advanced physical (PHY) layer and the use of orthogonal resources at the medium access control (MAC) layer. In principle, different users can transmit in fully separate time-frequency slots, thus avoiding reciprocal interference. However, this beneficial effect strictly depends on the ability to identify those resources that are not occupied. In addition, the available spectrum is scarce and space diversity becomes a third optimization dimension in order to minimize the reciprocal interference.
In short-range C-V2X, two different approaches are defined for resource allocation, one under the control of the network, called Mode 3, and the other where decisions are VOLUME xxxx, 2018 1 arXiv:1807.10699v2 [cs.NI] 28 Nov 2018 fully distributed among nodes, denoted as Mode 4. Although Mode 3 is expected to outperform Mode 4 given the more information available at the scheduler [2], [3], still problems could arise at the cellular boundaries (especially with different operators) and the latter remains the only option when coverage is intermittent or not available.
Given its crucial importance and in order to make products from different vendors interoperable, a Mode 4 algorithm is defined by 3GPP in [4], [5]. Outside 3GPP, still few works have investigated its performance and the impact of the various parameters. A study is presented for example in [6], where the authors compare Mode 4 to a random selection of resources. Results, in terms of delivery rate, are provided in a Manhattan grid scenario. The same authors extend the investigation to a highway environment in [7], while in [8] an analytical model is proposed in simplified scenarios. Furthermore, in [9] Nguyen et al. compare Mode 4 with a controlled allocation scheme and with IEEE 802.11p. All these works assume fixed and arbitrary settings of the parameters. Some very recent works have focused on the impact of the parameters, limiting their studies to specific aspects and showing that the settings can significantly affect the performance [10], [11].
Although several papers have recently concentrated on Mode 4, they have all posed the attention on specific aspects and one or few parameters. To cope with this limitation and to provide an in-depth discussion of Mode 4, here we focus on the main parameters defined at the PHY and MAC layers, considering both those that can be adjusted by specification and those that are instead mandate to a given value. The study will focus on the semi-persistent scheduling (SPS) related to the cooperative awareness service, which is the periodic broadcast of updated information by all vehicles about their status and movements and is at the basis of most of the applications foreseen for connected vehicles [12], [13]. The impact of each parameter and its optimal setting is derived through large-scale simulations in three realistic scenarios with hundred of nodes, using LTEV2Vsim [14].
In summary, the contribution of the paper is as follows.
• The performance of C-V2X Mode 4 is shown in realistic urban and highway scenarios, varying all main parameters at PHY and MAC layers; • We evaluate the impact of each parameter, starting from, but not constrained to, the values indicated by 3GPP, and identify the optimal settings; • Based on the results, guidelines for future improvements of the C-V2X Mode 4 algorithm are provided.
The rest of the paper is organized as follows: in Section II, the main characteristics of short-range C-V2X are summarized and the Mode 4 algorithm is briefly introduced; in Section III, the models and settings adopted for numerical results are detailed; Sections IV and V then focus on the impact of parameters at the PHY and MAC layer, respectively, followed by summary results and discussion in Section VI; finally, in Section VII we provide our conclusions.

A. LTE-V2V
The concept of D2D communications was initially introduced in Release 12 of LTE using the term sidelink to differentiate from downlink and uplink. The new interface for this scope, called PC5, was explicitly designed for proximity services, and has been enhanced in Release 14 to address also vehicular scenarios, where the high mobility of nodes and the possibly high carrier frequency make the channel estimation more challenging.
The new technology, hereafter denoted as LTE-V2V to highlight the reference to the present release of the standards (i.e., LTE) and the case of car-to-car communication, is part of the C-V2X, which promises to cover all use cases in a single chipset and to provide a continuous evolution with backward compatibility in the following releases.
Like LTE uplink, LTE-V2V adopts single carrierfrequency division multiple access (SC-FDMA) at the PHY and MAC layers, with the time-frequency domains organized into orthogonal resources called resource blocks. Resource blocks are allocated in pairs, corresponding to 180 kHz bandwidth (12 subcarriers with 15 kHz space) and 1 ms duration (14 OFDM symbols, of which 9 carry data, 4 are used for channel estimation, and one for timing adjustments and possible tx-rx switch). The minimum allocation time interval is 1 ms and is also denoted as transmission time interval (TTI). In LTE-V2V, resource blocks are also grouped in the frequency domain into subchannels, which are all of a given size (set by the network, with the constraints detailed in [15]). Each subchannel can carry at most one data packet, although one data packet can span over more than one subchannel. More specifically, each data packet, also known as transport block (TB), has an associated control message, called sidelink control information (SCI), which requires 2 pairs of resource blocks. A TB and the associated SCI must be transmitted in the same subframe, but can be allocated on adjacent or non-adjacent resource blocks. In the former case (adjacent), subchannels carry both TBs and SCIs, with the SCI transmitted in the first allocated subchannel. In the latter case (non-adjacent), specific resources are reserved for SCIs and subchannels are only occupied by TBs. The number of subchannels allocated to carry a packet depends on the kind of allocation, the subchannel size, the TB size, and the adopted modulation and coding scheme (MCS).
As mentioned, LTE-V2V has two possible approaches to allocate the resources for transmissions, namely Mode 3, where the network is in charge of performing the allocation and communicating it to the vehicles via signalling channels, and Mode 4, not requiring any intervention by the network. In both cases, a key traffic flow to be allocated is given by the cooperative awareness service, which means the broadcasting from each vehicle of periodic messages, hereafter called bea-FIGURE 1: Example of BRs in the time and frequency domain. In the example, there are four BRs per subframe (in the frequency domain) and one beacon period T B lasts six TTIs, T sense = 3 T B , T 1 = 2, T 2 = 5. It follows R = 4 · 6 = 24, of which 16 are within T 1 and T 2 . Assuming R sel = 0.2, the number of BRs passed to the MAC layer is n R = 4. cons 1 , detailing their status and movements. This service will play a key role in future CAV networks for both safety applications and data routing, since it allows each node to have continuously an updated knowledge of its neighbourhood. Given the periodic nature of the transmissions, allocations are in such case performed on an SPS basis, where the same subchannels are periodically reserved for some time in order to reduce the associated signalling.
The algorithm detailed by 3GPP for Mode 4 is divided into a PHY layer part [4] and a MAC layer part [5]. Hereafter, we provide a brief overview, whereas details on each of the mentioned parameters will be given later in Sections IV and V. An example, including most of the described parameters, is shown in Fig. 1. Before entering in the description of the algorithm, we will introduce the concept of beacon resource (BR), largely used in the further.

1) Beacon resources (BRs)
The objective of the algorithm is to identify an appropriate group of subchannels to allocate one beacon, with the aim to maximize the probability of correct reception by neighbour-VOLUME xxxx, 2018 ing vehicles. Given the periodicity (a message every beacon period T B ) and adopting the SPS approach, once a beacon is allocated, the same subchannels are kept every T B for a given time. This implies that the selection process focuses on the next time window lasting T B and on all the groups of subchannels able to carry the beacon during that interval. Such groups are hereafter denoted as BRs and correspond to the single-subframe resources of 3GPP in [4].
Given the size of the beacon, its generation periodicity, the used MCS, the size of subchannels, and the adjacent/nonadjacent allocation of SCIs, the generic node can calculate the number of messages that can be allocated in each subframe and create the time-frequency grid of BRs in one beacon period T B . The number of BRs in one T B will be denoted as R. Please remark that the BRs are in principle orthogonal to each other (they do not interfere), except for some in-band emission (IBE) when they share the same TTI.

2) PHY layer
At the PHY layer, the node continuously reads decodable SCIs and measures the average interference in each BR, with the aim to estimate the occupation of the BRs in the next T B . Measurements older than a given period T sense are discarded, thus T sense represents a sensing interval.
Given this information, the node focuses on the portion of BRs in the next T B that lay in an interval T 1 to T 2 TTIs, where T 1 and T 2 are parameters. Within this portion, the node considers as candidates only those that 1) have been monitored; e.g., due to half duplex limitations, a node cannot sense during a TTI if it transmits; 2) are estimated as not used, either because known as not occupied by the associated SCI or since the average measured reference signal received power (RSRP) is below a given threshold P th . The node then sorts the candidate BRs in terms of average sidelink-received signal strength indicator (S-RSSI) and selects the portion n R with the lowest value, where n R = R sel · R , R sel is a parameter, and · is the ceiling function. If the number of candidates is smaller than n R , then P th is increased by 3 dB and the previous steps are repeated. Once the required number of BRs is reached, those selected are passed to the MAC layer.

3) MAC layer
At the MAC layer, a BR is randomly selected among the received n R . Given SPS, the BR is then reserved for a certain number of beacon periods, randomly selected within n min and n max .
Once this time interval expires, a new resource allocation is performed with probability 1 − p k . If a reallocation is commanded, the new BR is again randomly selected within the n R received from the PHY layer. If a reallocation is not commanded (i.e., with probability p k ), the same BR is kept. Both if a new allocation is performed or not, a new random duration is set following the described rules and the process continues.

III. MODELLING AND SIMULATION SETTINGS
The results shown in the further have been obtained using the LTEV2Vsim simulator [14], which was designed for the investigation of resource allocation algorithms in C-V2X. In this section, a brief description of the main models and settings used for the simulations is provided. The main settings are also summarized in Tables 1 and 2, together with the values adopted if not differently specified.

A. COOPERATIVE AWARENESS SETTINGS AND DEFINITION OF NEIGHBOUR
To simplify the scenario, we assume that all nodes have messages of the same size, generated at the same frequency, and transmitted using the same MCS. Given these assumptions, the BR grid and the number of beacon resources R is the same for all vehicles. Please note that adopting the same size for all messages is equivalent to assume different sizes transmitted using the same number of resource blocks (as done for example in [9]) and focus the performance investigation on the largest one as the worst case. 2 Beacons are assumed of size B, with periodicity f B . Equivalently, beacons are periodically generated with a constant periodicity T B = 1/f B . In particular, f B is set to 10 Hz, which is the value most commonly adopted and B = 300 bytes, which is the largest size suggested by 3GPP in [18].
Beacons are broadcast, thus each of the other vehicles is a potential receiver. However, the importance of a message reduces with the distance. For this reason, we focus on a given maximum distance, set to 100 m in the urban and 200 m in the highway scenarios, and we denote as neighbours all the vehicles within such range from the source.

B. OUTPUT METRICS
The following output metrics will be used.
• Packet reception ratio (PRR): the average ratio between the number of neighbours correctly decoding a beacon and the total number of neighbours; • Update delay (UD): given a destination and source couple, it is the time difference between the instant a message is correctly received and the instant the last of the previous messages was correctly received. The UD quantifies how long a node does not receive any update from one neighbour and implicitly gives information about the correlation among errors.

C. SCENARIOS
Results are provided in the following three scenarios.

D. PROPAGATION AND SETTINGS AT THE PHY LAYER
All devices are assumed transmitting with 23 dBm power and using antennas with 3 dB gain. As for the propagation, the WINNER+ model, scenario B1, is adopted as recommended by 3GPP in [18]. The model also includes log-normal correlated shadowing, with variance 3 dB in LOS and 4 dB in NLOS and with decorrelation distance 10 m in urban and 25 m in highway scenarios. A packet is assumed to be correctly received if the corresponding signal to noise and interference ratio (SINR) is larger than a minimum threshold. All details about the calculations, which take into account cochannel interference and IBE, are provided in Appendix A.
The typical channel bandwidth of 10 MHz is assumed, which corresponds to 50 pairs of resource blocks per subframe. A non-adjacent allocation of SCIs, with four subchannels of 10 pairs (and the remaining used by the SCIs) are assumed.
Preliminary simulations have been then performed to set the MCS per each scenario. With the given assumptions, the options are to either allocate in each subframe one beacon occupying four subchannels with MCS 4, or two beacons occupying two subchannels each with MCS 7, or four beacons, one per subchannel, with MCS 14 (all the other MCSs would reduce the reliability without reducing the occupation of subchannels).
In Fig. 3, the PRR is shown for MCS 4, 7, and 14 in the three scenarios. In general, the PRR is higher in the Highway scenario since there are no buildings impairing the communication and all links are in LOS. Comparing the various VOLUME xxxx, 2018 MCSs, it can be noted that the results are the consequence of a trade-off: on the one hand, a higher value implies more available BRs, thus a lower collision probability, while on the other, increasing the MCS raises the required minimum SINR, thus causing a higher probability that the received power is insufficient. As observable, the best performance is provided by MCS 4 in the lightly loaded scenario of Cologne, where there are on average less competing nodes, and by MCS 7 in the other two. For this reason, these MCSs are adopted in the further and it follows that R = 100 in the Cologne scenario and R = 200 in the Bologna and Highway scenarios.

E. PRELIMINARY CONSIDERATIONS: HIDDEN NODE PROBABILITY
Before discussing the impact of the various parameters, it is interesting to estimate how frequent is the event that an interfering signal is not revealed by a node, thus making the sensing procedure ineffective. To this aim, we calculate the probability that an interferer is not sensed, hereafter called hidden node probability, as detailed in Appendix B.
The hidden node probability varying the sourcedestination distance d sd is shown for the three scenarios in Fig. 4. As expected, the hidden node probability is negligible when the source is near to the destination and then increases when the distance rises. Some differences can be observed in the three scenarios, due to the peculiar road topologies. In particular, especially for short distances, the absolute values vary among all scenarios and a non-monotonic behaviour can be noted in Cologne and Bologna. This is a direct consequence of the LOS/NLOS conditions, that strictly depend on the length of the road segments and the number of intersections.
As the main derivation from Fig. 4, it is important to note that the hidden node probability remains limited within reasonable distances. In particular, it results below 10% up to 50 m in the urban scenarios and almost 150 m in the Highway and do not exceed 30% as a worst case within the distances considered hereafter (i.e., 100 m in urban, 200 m in Highway). This implies that the sensing procedures are indeed potentially effective against most interferers.

IV. IMPACT OF MODE 4 PHY SETTINGS
As discussed in Section II-B and summarized in Table 1, the algorithm is characterized by several parameters at both PHY and MAC layers. In this section, the possible values of those at the PHY layer and their impact will be detailed. Since PRR and UD lead to the same conclusions, curves are shown only in terms of PRR to limit the number of figures; comments to UD are provided only when relevant. risk of inaccurate or outdated measurements. In principle, the lower it is and the better is the estimation for the next future. At the same time, however, it must be long enough to individuate at least one transmission from all neighbouring vehicles, i.e., it should be longer than their beacon period. In the standard, the value is fixed by specifications, depending on the duplexing type, and normally corresponds to 1 s. Please note that 1 s allows to sense at least one transmission from any node having a beacon periodicity of 1 Hz, which should be the lowest value under normal operation conditions. The impact of a variation of T sense in the investigated scenarios is provided in Fig. 5(a). As expected, except for Cologne, where the sparsity of the network makes results negligibly dependent on T sense , PRR reduces increasing T sense . What is interesting to notice is that a high impact on PRR is observable when T sense gets lower than 1 s (up to 10% higher PRR). As explained previously, this is indeed coherent with the presence of a beacon period of 100 ms. For the same reasons and given that higher beacon periods are possible, simply reducing T sense below 1 s is not a viable solution in general. However, the significance of the improvement suggests that some effort could be posed to enhance the algorithm, for example by either making it variable with the settings of the neighbours or adding mechanisms that better identify and discard the outdated information.
2) Power threshold P th defines a power level below which a BR is assumed as available, independently on what inferred from the decoded SCI. This allows to control the interference level that is considered acceptable and make the selection process more or less stringent. P th is set by the upper layers, depending on the priority a of the transmitter and b of the receiver (both within 0 and 7). Specifically, it is set to a value in the range [−128, −2] dBm following the formula The impact of P th is shown in Fig. 5(b). As observable, the     Table 1 are used for those settings not explicitly indicated.
impact is irrelevant in both Cologne and Highway. Only in Bologna, a small P th is shown to improve the performance of about 5% compared to a high P th . In this case, there are a few congested intersections, where vehicles have more than 70 neighbours in a range of 100 m. To better understand these results, please recall that only a portion of the resources assumed available will be then passed to the MAC, starting from those that have less interference. This implies that P th is relevant only if a very large number of resources is affected by an interference higher than P th , thus in very dense scenarios. Summarizing, the lower is P th and the higher is the PRR, although some impact is only observable in crowded conditions.

3) Portion of resources
The parameter R sel is then set to control the number of BRs passed to the MAC layer. R sel is fixed to 0.2 by specifications.
Apparently, the lower is R sel , the higher is the probability to select a resource with negligible interference, thus a smaller R sel might be expected to perform better. Indeed, this effect can be observed in Fig. 5(c), even if the variation of PRR is very small: if we look at Bologna and Highway, a slight decrease while increasing R sel can be noted, especially with R sel ≥ 0.1. However, with simulations not shown here for brevity, it was noted that a too low R sel causes a slight increase in some cases. 3 With a smaller set of resources for the random selection of the BR, in fact, the risk of a collision increases if the choice is performed by two nodes at the same time from the same pool. And having the same pool is rather frequent for nodes that are located near to each other and thus sense similar interference. This condition becomes    (3) and (4), whereas dots correspond to simulations used to validate the analysis.
anyway relevant only when the number of neighbours is very high compared to the number of resources. To summarize, the value 0.2 given by the standard appears as an acceptable compromise, even if 0.1 brought us to a small improvement (2-3% in our experiments).

4) Time window
T 1 and T 2 are two further parameters at the PHY layer that allow to restrict the interval of the allocation. The former, which must be between 1 and 4, indicates the first TTI where the allocation can be performed and gives a time margin to the device for the selection process. The latter, between 20 and 100, sets the last possible TTI and is used in the case of stringent delay requirements. The results, shown in Fig. 5(d) for three combinations of T 1 and T 2 , show a negligible difference in terms of PRR. In terms of UD we noted a very slight increase only with T 1 = 4 and T 2 = 20, confirming the intuitive conclusion that a larger time window better randomizes the resource selection among the various users. The value of T 1 and T 2 should thus be reasonably set to maximize the window, once the constrains on processing and delay are applied.

V. IMPACT OF MODE 4 MAC SETTINGS
In this section, the attention is moved to the MAC layer. The main parameters, summarized in Table 1, are: • Time before evaluation. Parameters n min and n max define the minimum and maximum number of beacon periods before a reallocation is considered (only considered and not always performed, as later clarified). Such an interval will be hereafter denoted as time before evaluation (TBE). The actual duration is randomly selected with uniform distribution within n min and n max . By standard, they are respectively fixed to 5 and 15 for a beacon periodicity of 10 Hz (higher values are defined for smaller frequencies); this means that the same RB is allocated for a duration that ranges between 0.5 and 1.5 seconds; • Keep probability. Once the selected number of beacon periods has expired, a new allocation is performed with probability 1 − p k . Equivalently, with keep probability p k , the same allocation is maintained for another random number of beacon periods. The value of p k can be chosen between 0 and 0.8. Parameters n min , n max , and p k together determine the distribution of the duration of an SPS allocation before a different scheduling is performed, hereafter denoted as time before change (TBC). Directly related to p k , one TBC is composed of a variable number of TBE; each TBE is in turn of variable duration, which depends on n min and n max .
It must be noted that an increase of TBC has two opposite effects: on the one hand, it makes the use of the channel more stable, thus making the sensing from neighbouring nodes less affected by outdated information (recall the discussion on T sense ); on the other hand, possible wrong selections are maintained for more time (for example, if two nearby nodes select the same resource they remain invisible for longer).
These two opposed effects are hereafter better highlighted, first focusing on specific metrics in a simplified scenario, and then showing PRR and UD in the realistic ones. With the sake of focusing on relevant cases, we compare five representative combinations: three with n min = 5 and n max = 15, varying p k from 0 to 0.4 and 0.8; the other two, assuming n min = 10, n max = 20, p k = 0.4 or n min = 10, n max = 30, p k = 0.
probability that the duration of one TBE is equal to a number n > 0 of beacon intervals T B is which can be re-written in the form of vector P TBE (P TBE (1), P TBE (2), ...). As a consequence, the probability distribution P TBC (n) that the same allocation is kept for a given number n of beacon periods is then obtained as where F d {·} denotes the discrete Fourier transform and the power raised to the vector denotes its application to each element. The demonstration is in Appendix C. P TBC (n) quantifies the duration before reallocation and should not be too large to avoid that unfortunate allocations last for too long. With trivial elaborations from P TBC (n), in Fig. 6(a) it is shown the complementary cumulative distribution function (ccdf) of the time before reallocation. Simulation results that validate the analysis are also shown. As observable, if n min = 5, n max = 15, and p k = 0.8, the probability that the same resource is maintained for more than 10 seconds is approximately 0.1. This could be extremely dangerous, since it implies that two neighbouring vehicles simultaneously selecting a resource of the same TTI (recalling the half duplex limitation) will remain hidden to each other for more than 10 s in 1 case every 100.
Looking now at the negative effect of a short time before reallocation, from (3) we also derive the probability to observe a change during the sensing interval, which causes a wrong view of the occupied resources. To this aim, the probability that a change is performed within a given interval of n * beacon periods P r (n * ) is obtained as The proof is in Appendix D.
Assuming T sense is a multiple of T B , the probability that a change is performed during the sensing interval is P r (T sense /T B ), which should be obviously as close as possible to zero: in fact, all measurements performed during T sense before the change alter the correct view of the interference. Results varying T sense are shown in Fig. 6(b). Simulations that validate the analysis are also shown. As observable, if the standard [5,15] is assumed with p k = 0, the probability to have a change during T sense = 1 s is 0.9, which means that 90% of the sensed nodes have changed their allocation during the sensing interval. This very high probability reflects on an inaccurate estimation of the interference and thus a reduced efficiency of the sensing process.

B. SIMULATIONS IN THE INVESTIGATED SCENARIOS.
Simulation results in the considered scenarios are then shown in terms of PRR and 99.99% of UD in Fig. 7.
As observable, again the impact of different combinations of n min , n max , and p k have opposed effects on PRR and UD. Whereas increasing any of the values have a positive impact on PRR due to an higher stability on the resource usage and thus a more efficient sensing process, the impact is negative on the update delay, because the duration of wrong allocations is statistically longer. This effect makes plain that the optimal definition of the parameters at MAC layer is subject to an unavoidable trade-off.
Another interesting point is that acting on the window does not lead to significant improvements. This means that the VOLUME xxxx, 2018 modification of p k is enough to control the trade-off between PRR and UD and there is no necessity to modify n min and n max .

VI. SUMMARY RESULTS AND DISCUSSION
In Fig. 8 and Fig. 9, the PRR and UD are respectively shown for all the addressed scenarios. The former shows the PRR varying the source-destination distance d sd , while the latter provides the UD correspondent to a target percentile, varying such target. In each sub-figure, five curves are compared, corresponding to the following allocations: • IEEE 802.11p (with CSMA/CA, hidden terminals, capture effect, and so on), adopting QPSK with 1/2 coding rate, which corresponds to 6 Mbps raw data rate and is the MCS normally used by default; • Random, meaning that each vehicle changes allocation every T B , selecting one of the R BRs at random; • Standard protocol, with p k = 0 (the minimum) and the other parameters set as in Table 1; • Standard protocol, with p k = 0.8 (the maximum) and the other parameters set as in Table 1; • An optimized Mode 4 where p k = 0.8, P th = −128 dBm, and some parameters are changed outside the specifications, with particular reference to T sense = 0.1 s and R sel = 0.1.
IEEE 802.11p is considered as a benchmark technology for this application. The random allocation is also used as benchmark, since it is the simplest way to allocate resources in LTE-V2V. Then, in addition to considering the standard protocol with the two extremes of p k , the last item corresponds to the maximum PRR obtainable with the detailed algorithm by modifying all parameters. From Fig. 8 and Fig. 9, the following observations can be derived.

1) LTE-V2V vs. IEEE 802.11p
Focusing on the PRR in Fig. 8, thanks to the more advanced PHY and MAC protocols LTE-V2V Mode 4 is shown to outperform IEEE 802.11p in almost all situations, especially if p k = 0.8 is assumed in LTE. It is however to note that the gap between the technologies is not as large as presumable. The superiority of LTE-V2V is more debatable if we now focus on the UD in Fig. 9. In some cases, such as with target 0.999 in Bologna, the update delay of IEEE 802.11p is indeed lower than with LTE; this is due to a significantly lower correlation between errors that follow the CSMA/CA protocol.

2) Random allocation
Using the random allocation as a reference, all curves in Fig. 8 give evidence that Mode 4 is effective in the identification of the free resources and the consequent spacial reuse. At the same time, Fig. 9 illustrates how this comes at the cost of a higher correlation in the errors. If we focus as an example on the Highway scenario, when a target 0.999 or    Table 1 are used for those settings not explicitly indicated.
more is considered, Mode 4 has an update delay which is double or more than with the random allocation.

3) Standard Mode 4
Restricting the observation to Mode 4, it can be noted that p k = 0.8 allows to improve PRR at the cost of a higher UD. The improvement in terms of PRR (Fig. 8) is negligible in Cologne, where the scenario is sparse, but becomes clear in both Bologna and Highway. The impact in terms of UD (Fig. 9) requires a more careful discussion: it can be noted, in fact, that p k = 0.8 allows also a lower UD until for values of the target percentile below a given threshold (between 0.997 and 0.998), but causes a higher UD above it. As discussed in Section V, this behaviour is a consequence of longer intervals with the same allocation when p k is higher; with p k = 0.8, wrong estimation of occupied resources is less probable, with lower UD at low target percentile, but an error causes longer bursts of errors, implying higher UD at higher target percentiles.

4) Mode 4 with Optimized Parameters
In Fig. 8 and Fig. 9, we also show the performance obtained by optimizing the Mode 4 parameters as discussed in the previous sections and summarized in Table 1. The clear result is that some margin for optimization in terms of PRR is possible, even if small and limited to very crowded situations (i.e., in Bologna). The impact to the UD is not remarkable, with a slight improvement compared to the standard Mode 4 with p k = 0.8 in the congested scenarios and a negligible worsening in the Cologne scenario.

5) Comparison with related work
The discussed results appear consistent with those presented in the related work. Specifically, focusing on a highway scenario, in [11] the authors show that PRR improves increasing p k , which is in total agreement with Fig. 8(c). In [9], LTE-V2V is shown to outperform IEEE 802.11p both in urban and highway scenarios; the gap is doubled in the latter case; these results are fundamentally coherent with Figs. 8(a), Figs. 8(b), and Figs. 8(c), especially if a high p k is assumed. Finally, in [6], the authors show that with p k = 0 in a not congested urban scenario, Mode 4 provides a delivery rate not too much higher than a random allocation. Although we observed some improvement also in the (least loaded) Cologne scenario, the cited results appear compatible with the fact that reducing the density of vehicles from Highway to Bologna to Cologne, the gap between Mode 4 and a random allocation reduces (Fig. 8).

VII. CONCLUSION
In this work we have described the various parameters affecting the performance of the 3GPP Mode 4 algorithm of LTE-V2X. Results have been shown separating those acting at the PHY and MAC layer and performing simulations in three different realistic scenarios. The main conclusions, which also lead to the specific indications reported as the last column of Table 3, can be summarized as follows.
• The modification of all parameters appears almost irrelevant in scenarios with a low to medium number of vehicles, whereas it might become significant when congestions occur; • Most parameters at the PHY layer have a minor impact on the performance and should be set to the extremes allowed by the specifications: specifically, the threshold power to sense the resource as occupied and the first TTI for the next allocation should be set to the minimum, whereas the last TTI for the next allocation should be set to the maximum; • A minimum improvement is possible by reducing the portion of beacon resources passed to the MAC layer, presently fixed to 20% by the specifications; it has also been observed that the best number slightly varies with the density of vehicles; • Again at the PHY layer, some performance improvement can be achieved acting on the sensing period, which is currently fixed to 1 s; it however requires to rethink the way the channel is sensed, since just reducing it is against the fact that some nodes may be transmitting at 1 Hz; • At the MAC layer, by modifying the keep probability it is possible to trade-off between a higher packet reception probability and a lower update delay; the variation can be relevant; • The variability of the keep probability appears sufficient to control the system performance; thus, as defined in the specifications, it appears acceptable to have fixed values for the minimum and maximum number of beacon periods before a reallocation.

APPENDIX A: SINR CALCULATION
Given a generic node a, S a and B a will be respectively used to denote the set of subframes (we define a set for generality, although it will be always of one element in our case) and the portion of bandwidth where a transmits. Given the generic transmitter i and the generic receiver j, if S i ∩ S j = ∅, i cannot decode the message from j due to half duplex limitations. Otherwise, the message is correctly decoded if the average SINR, denoted as γ ij , is higher than a given threshold γ min . The average SINR is calculated as where ψ ab is the power received by b from a, P n is the average noise power, V is the set of all the vehicles in the scenario, K S (S a , S b ) is the portion of time when the two signals from a and b overlap, and K IBE (B a , B b ) is the IBE coefficient from a signal transmitted in the frequency portion B a to the frequency portion B b . K S (S a , S b ) is proportional to the number of subframes they overlap, with 0 if the two signals use different subframes and 1 if they use the same subframes. The IBE coefficient is calculated as detailed in [21], with a value of 1 if the signals overlap in frequency and a lower value otherwise.

APPENDIX B: CALCULATION OF THE HIDDEN NODE PROBABILITY
The hidden node probability shown in Fig. 4 is calculated as follows. We denote the set of all nodes at a given time instant as N . Then, any node in the scenario a ∈ N is a potential source and we define as a generic destination b any node that receives from a with sufficient signal to noise ratio (SNR), thus any b ∈ D a , with where ψ x,y is the power received by y when x is transmitting, P n is the noise power, and γ min is a suitable threshold. Furthermore, we denote as c the generic interfering node, which is any node that causes the SINR to become lower than the given threshold γ min (this excludes the nodes that are too far), which can be written as c ∈ I a,b , with Among all interfering nodes, we call hidden any node h that the source cannot hear, using the same threshold γ min as a discriminator. In formulas, h ∈ H a,b , where H a,b = h ∈ I a,b ψ h,a P n < γ min .
At a given instant, the hidden node probability P hn is calculated as P hn = a∈N b∈Da #H a,b #I a,b where #X is the cardinality of set X . Finally, the overall hidden node probability is given by the average of P hn over all considered instants, which in our case correspond to periodic samples of period equal to the beacon interval, i.e., T B = 100 ms.

APPENDIX C: DEMONSTRATION OF EQUATION (3)
Equation (3) gives the probability that the same allocation is kept for a given number of beacon periods, i.e., the probability that a TBC lasts for a given number of T B . Let us denote as N TBE the number of TBE of which the generic TBC is composed. The probability distribution P cond TBC (n, 1) that the same allocation is kept for a given number n of beacon periods, conditioned to the fact that the TBC is composed by a single TBE, is simply P cond TBC (n, 1) = P{P TBC (n)|N TBE = 1} = P TBE (n) . (6) Since the length of each TBE is independent to the others and given the definition of P TBE , the probability distribution P TBC (n|2) that the same allocation is kept for a given number n of beacon periods, conditioned to the fact that the TBC is composed by two TBE, becomes P cond TBC (n, 2) = P{P TBC (n)|N TBE = 2} = P TBE (n) * P TBE (n) where the symbol * denotes the convolution operation and the symbol · means the multiplication element-by-element of the vectors. The use of discrete Fourier transformations allows to convert convolutions into products. Straightforwardly, (7) can be generalized, for a generic number of TBE composing the TBC as where the exponent to the vector denotes its application to each element. Then, the probability that the TBC includes k TBE, denoted as P kTBE (k), is equal to the probability to keep it k − 1 times and do not keep it the last one, i.e., P kTBE (k) = P{N TBE = k} = p k−1 k (1 − p k ) .
Using (8) and (9) and summing up for a variable number of TBE, it follows (3).

APPENDIX D: DEMONSTRATION OF EQUATION (4)
Equation (4) corresponds to the probability that a change occurs within a given number of beacon intervals, i.e., the probability that a TBC ends within an interval of the given number of T B .
Let us focus on the last TBC that starts before the given observation interval. The probability to be calculated is indeed exactly equal to the probability that such TBC ends within the observation interval. Let us use l to denote the length (in number of beacon intervals) of the TBC and w that of the observed interval. The probability that a change occurs within w is obviously 1 if l ≤ w. If l > w, it depends on when it started: the change occurs if the interval does not start in the last l − w beacon intervals, which means, assuming equal probability that it started on a generic beacon interval before the observation interval not farther than w beacon periods, that a change occurs with probability (l − w)/l. Summarizing, the probability P cond r (w, l) to observe a change within the observation interval of length w, conditioned to having the length of TBC, denoted as D TBC and expressed in beacon intervals, equal to l is P cond r (w, l) = P{P r (w)|D TBC = k} = 1 w ≤= l l−w l otherwise .
(10) The probability that a change occurs within the observation interval can then be easily calculated, using (10) and (3), as the probability that no change occurs later than the given observation interval, leading to (4).


extfieldsofstudy:
Medicine
Computer Science
Mathematics

text:
Optimization of Thurston’s Core Entropy Algorithm for Polynomials with a Critical Point of Maximal Order

This paper discusses some properties of the topological entropy systems generated by polynomials of degree d in their Hubbard tree. An optimization of Thurston’s core entropy algorithm is developed for a family of polynomials of degree d.

Introduction
The topological entropy of a polynomial P, denoted by P allows us to measure the complexity of the orbits of the dynamical system generated by P. This concept has been used to classify the dynamics in different polynomial families, for example, in the case of real one-parameter families of polynomials of degree 2, it has been shown that the entropy behaves monotonically [1,2]. For real cubic maps, it was shown that each locus of constant topological entropy is a connected set [3]. Later, this result was shown for a quartic polynomial family and for real multimodal maps [4,5]. In the complex polynomials family, the entropy is concentrated in the Julia set; it is constant and only depends on the degree of the polynomial family [1,6]. In order to study the dynamics of a polynomial with a finite postcritical set, Douady and Hubbard introduced the Hubbard tree; the theory of admissible Hubbard trees and critical portraits was later studied by Poirier [7]. Afterwards Thurston proposed to study the entropy, restricted to its Hubbard tree, of a polynomial with finite postcritical set, which, in this setting, is called the core entropy. He showed that the core entropy generalizes the concept defined for an invariant interval in the real case [8]. Furthermore, Thurston proposed an algorithm in order to calculate the core entropy. It is based on a linear transformation A (defined in terms of the external arguments of the postcritical set) whose spectral radius coincides with the core entropy [9].
In the case of the quadratic family, Li proved that the core entropy grows through the veins of the Mandelbrot set. Later Tiozzo proved, for the same family, that the core entropy can be extended as a continuous function of the external argument on the boundary of the Mandelbrot set [10,11]. He generalizes this result for polynomials of higher degrees [12].
In this article, we show a simplification of Thurston's algorithm for a family of polynomials of degree d ≥ 3 with one free critical point and one fixed critical point of maximum multiplicity. We always assume that the free critical point is either periodic or eventually periodic. According to [13], this family is conjugated to The polynomial function P a (z) has two critical points: zero which is the fixed critical point of maximal multiplicity and −a which is the free critical point. The parameter space of this polynomial family has been studied by Milnor [14,15] in the cubic case, and by Roesch [13], who studied the topological properties of the hyperbolic components in the case of degree d ≥ 3.
To simplify Thurston's algorithm, we construct a linear transformation A with a definition based on the external arguments of the orbit of the critical point (−a). As we will show, this linear transformation is defined in a space with smaller dimension than the one proposed by Thurston. Consequently, the spectral radius is easier to calculate. Here is the main result of this paper.
Main Theorem. Let P a be a postcritically finite polynomial of the family (1). If A denotes the matrix obtained via Thurston's algorithm, then A and A have equal spectral radii ρ.
In order to prove the Main Theorem, we use of the concept of external rays, the Thurston algorithm, and some properties of the entropy and non-negative matrices [16][17][18][19][20].

Thurston's Algorithm
The algorithm proposed by Thurston allows us to compute the core entropy of a polynom of degree d. With the purpose of defining this algorithm, we present some needed concepts which can be found in the work of Gao, [9].

The Algorithm of Thurston for Polynomials of Degree d
Let P(z) be a postcritically finite polynomial of degree d. Thus, P(z) has exactly d − 1 critical points, say, c 1 , ..., c n (counting multiplicities). Each c i is either in the Julia set, J p , or is the center of a Fatou component. Furthermore, J p is locally connected [18,21]. The algorithm is based on the analysis of the external rays that land either on the critical points or on the boundaries of Fatou components that contain the critical points.
Definition 1. We say that an external ray R(θ) supports a bounded Fatou component U if: (1) The ray lands on a point q at the boundary of U.
(2) There exists a sector based at q, delimited by R(θ) and the internal ray of U that lands at q, such that the sector does not contain any other external ray that lands on q.
Given a postcritically finite polynomial of degree d and a critical Fatou component U, that is, a Fatou component containing a critical point, let δ = deg(P| U ). We define the set Θ(U) as follows: (1) If U is periodic with orbit U → P(U) → · · · → P n (U) = U, we build Θ(U , z , θ) for all U in this orbit simultaneously. Using the Böttcher coordinates in U, we can find z ∈ ∂U with internal argument 0. This z is a root of U, which depends on the choice of the coordinates. This means that z is a periodic point of minimal period on the boundary of U. This choice determines a root for each Fatou component (P k (U), for k = 1, 2 . . . , n − 1). We call this root a preferred root of P k (U). If U is any component in the cycle and z is its preferred root, consider a ray (R(θ)) which supports U at z . Define Θ(U , z , θ) to be the set consisting of δ U arguments of the support rays for the component U that are the inverse image of P(R(θ)).
(2) If the Fatou component U is strictly preperiodic, take n as the smallest number for which P n (U) is a critical Fatou component. Let z ∈ ∂U be such that P n (z) = γ(α), where γ(α) is the point where R(α) lands on ∂P n (U) and α ∈ Θ(P n (U), γ(α), α). Consider a ray (R(θ)) that supports component U which contains z. Define Θ(U, z, θ) as the set of the δ U arguments of the supporting rays of U that, under P n , go to R(α).

Remark 1.
For each critical Fatou component U, there exists, at most, a finite number of sets (Θ(U , z , θ)), each one dependent on the choice of the root (z) in U and the argument (θ). We can choose any of them and denote it by Θ(U).

Definition 2.
Let P be a polynomial with finite postcritical set. Let U 1 , ..., U n be the pairwise disjoint critical Fatou components, and let c 1 , . . . , c m be the critical points in the Julia set (m + n is the number of different critical points of P). The finite collection of subsets of the circle is called the critical marking of P, if each of the Θ(U i ) is chosen as in Remark 1 and each Θ(c j ) consists purely of the angles of the external rays that lands on c j .
. . , Θ l } be the critical marking of a polynomial P of degree d. We define the critical and postcritical sets of Θ as respectively, where τ : T → T is the function given by τ(θ) = dθ mod 1. From the definition of critical marking, it is easy to see that the following holds: 1. Each τΘ i , i ∈ {1, 2, . . . , l}, consists of a unique angle. 2. The convex hulls of Θ i and Θ j in the unit disk intersect each other in, at most, one point of T, Let D be the unit disk endowed with the hyperbolic metric. We identify any point in ∂D with the argument in T. By doing this, each angle in the circle is considered to be mod 1. A leaf is either a point in T or the closure in D of a hyperbolic chord (non-trivial). Indeed, from now on, each time we mention chord or hull in the disk, it will be in the hyperbolic sense. For each set (S ⊂ T), we denote the convex hull of S as a subset of D by hull(S).
Notice that any critical marking of a postcritically finite polynomial seen in the unit disk is a critical portrait.
. . , Θ l } be a critical portrait. Given any two angles x, y ∈ T that are not necessarily different, and an element Θ of Θ, we say that the chord xy crosses the convex hull, hull(Θ) if x, y / ∈ Θ, and xy hull(Θ) = ∅. In this setting, we also say that x, y are separated by Θ.

Definition 4.
Given any pair of angles x, y ∈ T, the separation set relative to Θ is the set {k 1 , ..., k p } where the chord xy successively crosses hull(Θ k 1 ), ..., hull(Θ k p ), Θ k j ∈ Θ, and no other element of Θ separates the angles x, y. We say that the angles x, y are not separated by Θ if its separation set relative to Θ is empty.
If P d is a polynomial with finite postcritical set, then each element of its critical portrait Θ is rational and post(Θ) is a finite set. Hence, it is possible to define the finite set S consisting of pairs (not ordered) of {x, y} with x = y ∈ post(Θ) as long as card(post(Θ)) ≥ 2. In the case of post(Θ) = {x}, S has only one element and in this case, x is a fixed point of τ.
Once we have defined the set S, the entropy of P d restricted to the Hubbard tree (H(P d )) is given by the Algorithm 1.

Algorithm 1 Thurston's Algorithm
• Let V be the vector space over R which has the elements of S as a basis.
• Let A : V → V be the linear transformation defined by the values on the basis S of V as follows.
For any vector ({x, y} ∈ S), the image is defined by • Let A be the matrix associated with the linear transformation A with respect to the basis S. As this matrix is non-negative, according to Perron-Frobenius Theorem, the spectral radius ρ of A is non-negative [16].
Theorem 1 (Gao). Let P d be a polynomial of degree d with a finite postcritical set, and let Θ be a critical marking for P d . If ρ is the spectral radius of the matrix in Thurston's algorithm, then h(H(P d ), P d ) = log ρ.
A full proof of the above Theorem can be found in [9]. One of the advantages of studying the entropy in the critical portrait is the fact that each point of the postcritical set corresponds to an angle in the set post(Θ) in such a way that any arc of H(P d ) between two vertices can be represented by some pair of angles, although possibly not in a unique way. Intuitively, one can think that the actions of P d in those arcs induce a transformation in the space generated by the pair of angles in the set post(Θ) given by the matrix A of Thurston's algorithm.

Thurston's Algorithm in the Polynomial Family (1)
Let P a be a polynomial in the family (1). The critical points of P a are 0 and −a. The point 0 is the center of the fixed Fatou component B a , and −a is a free critical point. If −a is the center of a Fatou component, then this component will be denoted by U 1 .
We also define the following set of angles where Θ(B a ), Θ(U 1 ) and Θ(c 1 ) are defined as in Section 2.1. Assume that P a has a finite postcritical set. The collection of angles Θ P a = Θ −a is called a restricted critical marking.
Let Θ P a be the restricted critical marking of P a . We define the restricted critical set and the restricted postcritical set as crit(Θ P a ) = Θ −a and post(Θ P a ) = n≥1 τ n crit(Θ P a ).
In the same way as we did before, we identify any point in ∂D with its argument in T. The restricted critical marking of P a viewed in D is denoted by Θ a . Lemma 1. If Θ a is the restricted critical portrait of the polynomial P a , then D \ hull(Θ a ) has 2 connected components with arcs in T of lengths 1 d and d−1 d , respectively.
Proof. Since deg(P| −a ) = 2, Θ a consists of two elements, the convex hull (hull(Θ a )) divides D in two regions. On the other hand, as the elements of Θ a are obtained as inverse images of the same angle, the arc length between the elements of Θ a is equal to 1 d (c.f. Proposition 2.31 in [13]). This completes the proof.

Definition 5.
Let Θ a be a restricted critical portrait. Given any two angles x, y ∈ T (not necessarily different), we say that the chord (xy) crosses the convex hull (hull(Θ a ) of Θ a ) if x, y / ∈ Θ a and xy hull(Θ a ) = ∅. Under these conditions, we say that x, y are separated by Θ a .
If P a has a finite postcritical set, then the elements of the restricted critical portrait are rationals, and post(Θ a ) is a finite set. We define set S as all pairs (not ordered) of {x, y} with x = y ∈ post(Θ a ) as long as card(post(Θ a )) ≥ 2. If post(Θ a ) = {x}, then S is the element {x, x}, and x is a fixed point of τ. Once we have defined set S , the adapted Thurston's algorithm that is used to approximate the entropy of P a over its Hubbard tree is given by Algorithm 2.

Algorithm 2 The Adapted Thurston's Algorithm
• Define V as the vector space over R which has the elements of S as a basis. • Let A be the matrix associated with the linear transformation A with respect to the basis S . This matrix is non-negative, and, according to the Perron-Frobenius Theorem [16], the spectral radius ρ of A is non-negative.

Theorem 2.
Let P a be a finite postcritical polynomial. If A denotes the matrix obtained by Algorithm 1, and A is the matrix generated by Algorithm 2, then A and A have the same spectral radius (ρ).
Proof. In order to prove the Theorem, we have to consider two cases: (1) If −a ∈ B a , in this case, the core entropy is zero, and we show that in the restricted algorithm. The spectral radius of matrix A is 1.
(2) If −a / ∈ B a , we show that transformation A can be built without considering the line of separation of the critical point (0).
Let P a be a polynomial of degree d with a finite postcritical set. In accordance with Böttcher's Theorem, a biholomorphism φ a exists that conjugates P a with the function z d in a neighborhood of infinity. Since P a is postcritically finite, its Julia set is locally connected; hence, φ a can be extended continuously to J a [21].
Moreover, the dynamics in B a are conjugated to z d−1 , and the conjugation can be extended continuously to the boundary; hence, a fixed point p of P a exists, with an internal angle of 0, that is, in ∂B a . The Böttcher coordinate is chosen at infinity in such a way that the external angle of p is also 0.
According to the above and the construction of the critical portraits, the set of angles is Hence, the critical portrait of P a is given by where Θ −a consists of two elements according to Lemma 1. This shows that for a fixed d, the postcritical set varies only in the function of the critical point (−a). On the other hand, the edges of the Hubbard tree are related to the pairs of angles in the critical portrait as follows: the interval of angles with extremes {θ 1 , θ 2 } in the circumference represents a union of edges in the Hubbard tree, and the interval of angles in the circle given by the image of A({θ 1 , θ 2 }) is equivalent to the interval of angles that contains the image under P a of the union of corresponding edges.

Remark 2.
If S denotes the basis of the vector space in Algorithm 1 and the pair {θ 1 , θ 2 } ∈ S is separated with respect to the critical line Θ c i , then the corresponding edge or edges contain the critical point c i .
Case 1: Let P a be a postcritically finite polynomial such that −a ∈ B a . As P a is conjugated to z d−1 in B a , then the tree of a is star shaped with n edges. We can label the edges in the Hubbard tree such that the incidence matrixÃ = (a i,j ) is defined by a i,i+1 = 1 for i = 1, . . . , n − 1, a n,j = 1 for some j ∈ {i, . . . , n} and zero otherwise.
The characteristical polynomial of the incidence matrixÃ is (−1) n λ k−1 (λ n−(k−1) − 1), and its spectral radius is 1. Hence h(P a ) = 0. On the other hand, Theorem 1 says that the spectral radius of A obtained by Thurston's method is 1.
Due to the fact that the orbit of −a is in B a , the restricted critical portrait Θ a consists of the external angles corresponding to the component B a . Hence, pairs ({θ i , θ j }) separated with respect to the critical point (−a) do not exist. Moreover, we can disregard the separation with respect to 0, as in the restricted algorithm. Thus, there is no pair that is separated. Consequently, all pairs {θ i , θ j } ∈ S have only one image. Furthermore, all rows of matrix A add up to 1; thus, the spectral radius is 1.
Case 2: If −a / ∈ B a , we have the next claim. In set S, in order to obtain the image of a separated pair ({θ 1 , θ 2 }) we can discard the characteristic of being separated with respect to the critical line of Θ 0 . Thus, for this family of polynomials, if the pair {θ 1 , θ 2 } is separated with respect to Θ, its separation set consists only of one element-the one associated with Θ −a .
Since the postcritical set of P a only depends on the critical point (−a), we can study them if we separate them into the following cases: (1) If −a is the center of a capture component, then the orbit of Θ −a eventually contains the zero angle, which is a fixed angle. In this case, the postcritical set of Θ is n≥1 τ n (Θ −a ). Hence, A = A .
(2) If −a eventually goes to p ∈ ∂B a , with a fixed p, then the orbit of Θ −a contains the zero angle; thus, as above, A = A .
(3) In any other case, the orbits of Θ −a and Θ 0 are disjoint. Hence, the postcritical set is If we write set S in such a way that the first k elements are of the form {0, θ i }, then S can be written as Hence, the matrix associated with the transformation A is where B is the submatrix corresponding to the relations of the images of the pairs of the form {0, θ i } with themselves, and C is the submatrix corresponding to the relations of the images of the pairs {θ i , θ j } with themselves. The lower submatrix N represents the relations between the images of pairs Since we do not consider the separation with respect to the critical line Θ 0 , and the orbit of Θ −a does not contain 0, the image of a pair {θ i , θ j } does not have a component of the form {0, θ l }. Hence, the matrix N is identically 0.
Since C is exactly the matrix A , to finish the proof of the theorem, it is enough to prove the following claim.
with a spectral radius of 1.3953.
As the above example shows, the Thurston restricted algorithm allows us to reduce the dimensions of the matrix as well as the cardinality of the orbit of −a. Furthermore, the sum of the elements of any row of A is, at most, 2, while the sum of the elements of a row in A can be greater than 2. Figure 3 shows the core entropy as a function of the external argument for d = 3.


extfieldsofstudy:
Medicine
Computer Science

text:
PredT4SE-Stack: Prediction of Bacterial Type IV Secreted Effectors From Protein Sequences Using a Stacked Ensemble Method

Gram-negative bacteria use various secretion systems to deliver their secreted effectors. Among them, type IV secretion system exists widely in a variety of bacterial species, and secretes type IV secreted effectors (T4SEs), which play vital roles in host-pathogen interactions. However, experimental approaches to identify T4SEs are time- and resource-consuming. In the present study, we aim to develop an in silico stacked ensemble method to predict whether a protein is an effector of type IV secretion system or not based on its sequence information. The protein sequences were encoded by the feature of position specific scoring matrix (PSSM)-composition by summing rows that correspond to the same amino acid residues in PSSM profiles. Based on the PSSM-composition features, we develop a stacked ensemble model PredT4SE-Stack to predict T4SEs, which utilized an ensemble of base-classifiers implemented by various machine learning algorithms, such as support vector machine, gradient boosting machine, and extremely randomized trees, to generate outputs for the meta-classifier in the classification system. Our results demonstrated that the framework of PredT4SE-Stack was a feasible and effective way to accurately identify T4SEs based on protein sequence information. The datasets and source code of PredT4SE-Stack are freely available at http://xbioinfo.sjtu.edu.cn/PredT4SE_Stack/index.php.

INTRODUCTION
Gram-negative bacteria use various secretion systems to deliver their secreted substrates (also called as effectors) from the bacterial cytosol into host cells, which can promote virulence and cause diseases. Until now, eight different secretion systems (type I to type VIII) have been found in Gramnegative bacteria, which differ from each other in their outer membrane secretion mechanisms. There are a number of well-organized databases or web resource on collecting experimentally validated effectors of Type III, IV, and VI secretion systems (Bi et al., 2013;Li et al., 2015;Eichinger et al., 2016;An et al., 2017). Among them, type IV secretion system (T4SS) exists widely in a variety of bacterial species, such as Bordetella pertussis, Helicobacter pylori, Coxiella burnetii, and Legionella pneumophila (Chandran et al., 2009;Fronzes et al., 2009;Lifshitz et al., 2013). T4SS specifically secretes type IV secreted effectors (T4SEs), which vary widely across bacterial species. T4SEs mimic the function of host proteins, exert vital functions in cytoplasm of infected eukaryotic cells and play crucial roles in host-pathogen interactions. Accurate and reliable identification of T4SEs is a crucial step toward the understanding of the pathogenic mechanism of T4SS. Due to the biological significance of T4SEs, a number of experimental approaches have been developed to identify novel T4SEs such as fusion protein report assays and secretion apparatus. However, these experimental approaches are timeand resource-consuming. It is highly desirable to develop in silico classification models to accurately predict type IV secreted effectors of T4SS based on protein sequence information.
In the last decade, several computational approaches using machine learning (ML) algorithms were developed to predict T4SEs based on protein sequence information. A pioneering method proposed by Burstein et al. (2009) formulated the task of identifying T4SEs on Legionella pneumophila genome as a classification problem using various ML algorithms, including naïve Bayes, Bayesian networks, support vector machine (SVM), Neural networks, and a voting algorithm that is based on these four algorithms. The input features of these algorithms include taxonomical dispersion, regulatory data, genomic organization, and similarity to eukaryotic proteomes (Burstein et al., 2009). Later, the same group developed a hidden semi-Markov model (HSMM) to characterize the amino acid composition of the secretion signal for identification of T4SEs across species (Lifshitz et al., 2013). Chen et al. (2010) used the similar ML-based model as the previous study (Burstein et al., 2009) to predict putative T4SEs in Coxiella burnetii genome, which helped narrow the number of potential targets for subsequent experimental validation. T4EffPred is a SVM-based prediction tool for identifying T4SEs based on four types of sequence-derived features, which were calculated from amino acid composition (AAC) and position specific scoring matrix (PSSM) profiles . T4SEpre (Wang et al., 2014) is another SVMbased tool for predicting T4SEs from C-terminal 100 amino acids of protein sequences by using AAC, position-specific AAC profiles, and predicted structural features such as secondary structure and solvent accessibility. An et al. (2016) constructed an ensemble model by random forest to integrate the output of the individual predictors (i.e., T4EffPred and T4SEpre) to improve predictive performance. Recently, Wang Y. et al. (2017) presented an effective method to predict T4SEs prediction by integrating information from both 50 N-terminal and 100 C-terminal residues of protein sequences. The model was built by SVM based on three types of features, namely AAC, PSSM, and composition, transition and distribution.
Overall, the currently available computational approaches for prediction of T4SEs vary from one another in terms of the utilized features and ML algorithms. Since the numbers of effectors and non-effectors in genomes are heavily unbalanced (the effectors comprise only a small fraction of a genome), it is highly desirable to develop a prediction method with high precision and high specificity. Otherwise, the number of true positives would easily be overwhelmed by the number of false positives, so that such a predictor is impractical to generate reliable candidates for experimental validation. In the present study, we aim to propose a stacked ensemble model, PredT4SE-Stack, to further improve the prediction performance (i.e., higher precision and specificity) for identifying T4SEs from protein sequence information. The stacked generalization approach (Wolpert, 1992) consists of an ensemble of base classifiers whose outputs are further learned by a meta-classifier to model the relationship between the ensemble outputs and the actual classes/labels. To construct the model, the protein sequences are firstly encoded by the feature of PSSM-composition by summing rows that correspond to the same amino acid residues in PSSM profiles. Based on the PSSM-composition features, a total of eight types of MLbased algorithms (including advanced ML techniques) are used to build base-classifiers in the first stage. Then, the optimal combination of base-classifiers is searched, and the output of these selected base-classifiers are utilized as input for a metaclassifier at the second stage. Our experimental results on both cross validation and independent tests demonstrated that the framework of PredT4SE-Stack is a feasible and effective way to accurately identify T4SEs based on protein sequence information. It also has achieved better performance than previously published methods.

Dataset
In this study, the same benchmark dataset curated by Wang Y. et al. (2017) was used to evaluate the performance of our proposed method. The dataset consists of 1,765 protein sequences across multiple bacterial species, categorized into two classes (380 T4SEs as the positive class and 1,385 non-T4SEs as the negative class). These proteins in this dataset have mutual sequence identity no more than 30%. The 1,765 protein sequences were divided into two subsets for cross validation in the training and the independent testing, respectively. The training dataset (Train-915) are composed of 915 sequences, among which 305 T4SE sequences were randomly selected from positive class, and 610 non-T4SE sequences were randomly selected from negative class. The dataset of Train-915 was further randomly divided into five subsets (or folds) with an equal number of protein sequences for cross validation to attain the optimized model. In each of the five validations, 4 of the 5-folds were used for training and the remaining one for testing, which was repeated for five times. The testing dataset (Test-850) included the remaining 75 T4SE sequences as positive samples and 775 non-T4SE sequences as negative samples for independent testing.

Feature Representation of Protein Sequence Samples
One of the key problems in designing a predictor based on machine learning is how to encode a protein sequence as an informative feature vector enriched with highly discriminative information. In the present section, we describe how to formulate an effective mathematical expression that describes protein sequences in the training and testing data sets.
The protein sequence profile (i.e., PSSM) is a powerful representation of residue or sequence information of proteins. It has achieved good performance on a number of bioinformatics applications such as functional residues prediction and protein function prediction (Xiong et al., 2011a(Xiong et al., ,b, 2012Zhu et al., 2013;Wei et al., 2017a). In this study, PSSMs were generated by three iterations of PSI-BLAST searches against Uniref50 with the BLOSUM62 substitution matrix. The parameter of e-value was set to 0.001. Because ML-based models can only handle vectors with equal lengths for all protein sequence samples, the PSSM of a protein sequence (amino acid length is L) has a dimension of L * 20, which could not be directly used as the input feature vector for machine learning algorithms. Instead, the original PSSM profile was further used to calculate the feature of PSSMcomposition by summing rows that correspond to the same amino acid residues in a PSSM profile, in much the same way as the previous studies Wang J. et al's., 2017). The sum value was divided by the length of the protein sequence for each type of amino acid (there is a total of 20 types). Thus, a vector of size at 400 (=20 × 20) is finally used for representing a protein sequence sample. Figure 1 presents the details about how to generate a feature vector of PSSM-composition for a given protein sequence.

Classification System
The ensemble learning techniques can be categorized into three main types, which include bagging, boosting, and stacked ensemble. It is demonstrated that the ensemble learning techniques can help improve the prediction performance in various bioinformatics applications Lin et al., 2013Lin et al., , 2014Zou et al., 2015;Li et al., 2016;Yuan et al., 2016;Wan et al., 2017;Iqbal and Hoque, 2018;Mishra et al., 2018;You et al., 2018). In this section, we introduce the components of the twostage stacked ensemble scheme, including various classification algorithms used as base-classifiers in the first stage, and the input of the meta-classifier in the second stage.

Base-Classifier
In order to find the optimal combination of base-classifiers in the first stage and the meta-classifier in the second stage, the following eight different machine learning algorithms were exploited: (i) SVM (Cortes and Vapnik, 1995) (Breiman, 2001), (vi) Extremely Randomized Trees (ERT) (Geurts et al., 2006), (vii) Gradient Boosting Machine (GBM) (Friedman, 2001), and (viii) eXtreme Gradient Boosting (XGB). The algorithms such as NB, LR, and GBM were implemented by using h2o package in R software. The algorithms of SVM, KNN, RF, ERT, and XGB are implemented by using e1071, caret, randomForest, extraTrees and xgboost packages in R, respectively. The optimal parameters in these algorithms are determined by a grid search strategy.

Meta-Classifier
The meta-classifier in the second level generalization (or stacked generalization) is used to combine the outputs of base-classifiers in an ensemble. In our classification system, we applied a stacked generalization approach proposed by Wolpert (1992), in which an ensemble of base-classifiers are first constructed, whose outputs are used as inputs to a second level of meta-classifier to learn the relationship between the ensemble outputs and the actual classes/labels. The stacked generalization scheme can be viewed as an extension version of cross validation. In the first stage, the base-classifiers were trained with the feature of PSSMcomposition of sequences. In the second stage, the prediction class probabilities of the base-classifiers were taken as inputs to the meta-classifier (shown in Figure 2).

Model Validation Method
To evaluate performances of classification models, the validation methods are mainly consisting of k-fold cross validation, leaveone-out cross validation (or called as jackknife test), and independent tests. In k-fold cross validation, the sample set is randomly divided into k subsets with equal sizes. Of the k subsets, only one subset is selected as the validation data for testing the model, and the remaining k-1 subsets are used as training data. The cross validation process is then repeated k times (the folds), with each of the k subsets used exactly once as the validation data. The results from k folds are finally averaged. The k-fold cross validation method has been widely used as the model validation approach in various bioinformatics applications (Zhu and Mitchell, 2011;Xu et al., 2017;Zeng et al., 2017;Chen X. et al., 2018;He et al., 2018a,d). In the present study, the 5-fold cross validation was used for validation in the training set, and the independent test was used for testing the generalization ability of the proposed method, and comparison with other methods.

Model Evaluation Metric
In order to assess prediction performances of single-label classification systems, a set of six threshold-dependent metrics are widely used in the bioinformatics studies (Xia et al., 2010;Li et al., 2011;Zhang et al., 2017Zhang et al., , 2018aHe et al., 2018c;Jia et al., 2018;Zhao et al., 2018). They are accuracy (ACC), sensitivity (SE, also called recall), specificity (SP), precision (PR), Matthew's correlation coefficient (MCC) and F-measure (F 1 ). The definitions of these metrics are shown as below.
where TP (true positives) is the number of correctly predicted T4SEs, TN (true negatives) is the number of correctly predicted   non-T4SEs, FP (false positives) is the number of non-T4SEs wrongly predicted as T4SEs, and FN (false negatives) is the number of T4SEs wrongly predicted as non-T4SEs. The receiver operating characteristic (ROC) curve is a plot of the sensitivity versus (1-specificity) for a binary classifier at varying thresholds from 0 to 1 (the threshold is assigned as the probability of the target sequence to be a T4SE in our study). The area under the curve (AUC) can be used as a powerful metric for evaluation performances of classifiers. It is worth mentioning that AUC of ROC (and ACC, MCC) can present overly optimistic assessment of performance of an algorithm on a heavily unbalanced dataset. Therefore, we only used AUC of ROC for evaluation in 5-fold cross validation, but not used it for evaluation in the independent dataset (only 75 proteins are true positives among 850 samples). Instead, the metric of F 1 , which is a harmonic mean of recall (or sensitivity) and precision, is a main metric for evaluating performances of classifiers in the present study.

Predictive Power of Various Base-Classifiers on Train-915 Dataset
The aim of this section is to test the predictive power of baseclassifiers based on PSSM-composition profiles for eight different machine learning algorithms on Train-915 dataset using 5fold cross validation. Experimental results shown in Table 1 indicate that the algorithm of naïve Bayes performed worst on this task. The algorithms of KNN, logistic regression, random forest, and extremely randomized trees performed moderately.
The algorithms of support vector machine, extreme gradient boosting, and gradient boosting machine performed best. The results of ROC shown in Figure 3 are mainly in agreement with the findings in Table 1. However, the fact that the AUC-ROC of SVM is higher than that of XGB and GBM indicates that SVM can achieve more stable performance than XGB and GBM using PSSM-composition feature as input in the present task, in regardless of the change of the thresholds. It should be noted that we tried a large number of other types of PSSMderived features generated by POSSUM tookit , and a variety of structural and physiochemical descriptors extracted from protein sequences generated by iFeature tookit  when we designed the input features of the base-classifiers. Our experimental results demonstrated that the PSSM-composition feature utilized in this study yielded satisfactory performance, which performed better than other types of sequence-based features. Moreover, we attempted to directly combine the PSSM-composition feature with other types of features as the input of the base-classifiers. It was found that the combined features could not significantly produce higher performance than the single type of PSSM-composition feature (data not shown).

Predictive Power of Meta-Classifiers on Train-915 Dataset
Since combining all of the above mentioned base-classifiers in a meta-classifier could not yield optimal prediction performance, it is desirable to search for the optimal combination of baseclassifiers. Since RF and ERT are tree-based classifiers, we chose   one of them at a time. Because GBM and XGB are boosting-based methods, and XGB is an efficient and scalable implementation of GBM, we chose one of them too. It was found that the combination of SVM, GBM, and ERT achieved the optimal performance, which is in agreement with the finding of study by Pan et al. (2018) on the prediction task of hot spots in protein-RNA interfaces. Furthermore, we tested the same set of eight ML methods as the classification algorithms of meta-classifiers to compare their prediction performances. The results in Table 2 showed that all meta-classifiers except the one based on ERT achieved very similar performances, for example, the values of F 1 are falling in a narrow range from 0.847 to 0.858, whereas the base-classifiers using the same set of ML algorithms are ranging from 0.669 to 0.847 in the first stage. These results can be explained by the fact that the pattern learned from the first stage is effective enough, leading to the similar level of performances at the second stage on the same dataset of Train-915, irrespective of ML algorithms, except ERT (also demonstrated in Figure 4) .

Predictive Power of Meta-Classifiers on Test-850 Dataset
In the section, the prediction performances of meta-classifiers are evaluated on the independent dataset, which is mimicking a true prediction task, since the model trained on one dataset is really tested on an unseen dataset for examining its generalization ability on a new dataset. Table 3 indicated that LR and SVM have top performances on Test-850 dataset. Therefore, both of them can be utilized as the classification algorithms of the metaclassifier in PredT4SE-Stack. Considering the fact that LR is more interpretable than SVM, we could use LR to construct the metaclassifier in our model PredT4SE-Stack. In real application, we will re-train PredT4SE-Stack on a whole dataset consisting of Train-915 and Test-850.

Comparison With Previous Studies
The main purpose of this section is to compare our proposed approach PredT4SE-Stack to previously published methods. Performance comparisons among different T4SE prediction approaches are scientifically meaningful only if they train and test their methods on the same dataset. Accordingly, our approach PredT4SE-Stack was only compared with the recently published method proposed by Wang Y. et al. (2017). The first reason is that both two studies used the same benchmark dataset  Table 4 in their published study, we firstly calculated the TP, TN, FP, and FN using the sensitivity and specificity of their method, and then calculated F 1 and precision of Wang Y. et al.'s (2017) method. The meta-classifier of our PredT4SE-Stack classification system was implemented by SVM or LR. For SVM or LR, the performance (F 1 = 0.734 or 0.733) of our method is much higher than that (F 1 = 0.521) of Wang Y. et al.'s (2017) method. If our SVM-based metaclassifier is tuned on the same recall or sensitivity of 90.7%, our method achieved better performance at specificity, precision, and F 1 , which are 2.4, 4.1, and 4.1% respectively, higher than that of Wang Y. et al.'s (2017) method. If our LR-based metaclassifier is tuned on the same recall or sensitivity of 90.7%, our method achieved better performance at specificity, precision, and F 1 , which are 3.7, 6.7, and 6.5% respectively, higher than that of Wang Y. et al.'s (2017) method.

CONCLUSION
The main goal of the current study is to develop a stacked ensemble model PredT4SE-Stack to predict T4SEs from protein sequence information. The proposed model utilized an ensemble of base-classifiers implemented by SVM, GBM, and ERT to generate outputs for the meta-classifier in the classification system. It was demonstrated that the framework of PredT4SE-Stack was a feasible and effective way to accurately identify T4SEs based on protein sequence information. However, the performance of PredT4SE-Stack can be further improved in several respects. Firstly, the diversity of base-classifiers was implemented by various classification algorithms in the present work. It can be further improved by different features in different base-classifiers. Secondly, inspired by the successful application of feature selection strategies in various bioinformatics tasks (Zou et al., 2016;Wei et al., 2017bWei et al., , 2018He et al., 2018b;Manavalan et al., 2018;Qiao et al., 2018;Su et al., 2018;Tang et al., 2018), the predictive power of base-classifiers can be boosted by incorporating an effective feature selection technology on a large pool of sequence-derived features. Moreover, an effective model selection on a large number of candidate base-classifiers will be explored to improve the prediction performance of the metaclassifier. These improvements will be explored in the further study.

AUTHOR CONTRIBUTIONS
XZ and D-QW conceived the study. YX and XZ designed the experiments. YX performed the experiments. YX, QW, JY, and XZ analyzed the data. YX and XZ wrote paper. All authors reviewed the manuscript and agreed to this information prior to submission.


extfieldsofstudy:
Computer Science
Engineering
Mathematics

text:
Learning from the Syndrome

In this paper, we introduce the syndrome loss, an alternative loss function for neural error-correcting decoders based on a relaxation of the syndrome. The syndrome loss penalizes the decoder for producing outputs that do not correspond to valid codewords. We show that training with the syndrome loss yields decoders with consistently lower frame error rate for a number of short block codes, at little additional cost during training and no additional cost during inference. The proposed method does not depend on knowledge of the transmitted codeword, making it a promising tool for online adaptation to changing channel conditions.

I. INTRODUCTION
Researchers are currently exploring the use of neural networks in digital communication systems, either as replacements for certain components or as an end-to-end solution. Much of this work has focused on trying to train improved decoders for error-correcting codes, since for many codes and channels the design of a near-optimal decoder is an unsolved problem. There have been many attempts to build machine learning-based decoders over the years [1]- [7], but these attempts have largely been thwarted by the "curse of dimensionality" described in [8]: for a code with k-bit messages, there are 2 k possible codewords, and a naïvely configured learning algorithm may not generalize to the many codewords not seen during training. Indeed, [9] found that a fully-connected neural network for decoding even the simple (7,4) Hamming code could not successfully decode received vectors corresponding to codewords never shown during training.
A few recent breakthroughs have reignited interest in the idea of decoding using deep learning. First, in [10], Nachmani et al. showed that by unrolling the belief propagation decoding algorithm for a number of iterations and assigning learnable weights to each iteration, a neural network is formed that can be trained to achieve error correction performance significantly better than that of the conventional belief propagation decoder for short high-density parity-check (HDPC) codes. Since the code is hardwired into the neural network structure, it suffices to train it using only the all-zeros codeword, thus sidestepping the curse of dimensionality. Subsequent works modified Nachmani et al.'s approach to be more hardwarefriendly [11], use fewer parameters through weight sharing and attain close to optimal performance by being combined with a state-of-the-art HDPC decoder [12], [13], and handle channels with correlated noise using a convolutional neural 1 The first author performed this work while at McGill University. network [14]. Second, in [8], Gruber et al. reported the same failure of fully-connected neural networks to generalize to new codewords as was originally reported in [9], but found that the effect was much less pronounced for codes for which the parity-check matrix is not random but rather has structure (specifically, polar codes [15]), suggesting that fully-connected neural networks are capable of learning something like a decoding algorithm rather than simply memorizing the code. The approaches in [16] and [17] strike a balance between fully-connected neural networks and conventional decoding algorithms to achieve lower latency decoding of polar codes.
Existing methods for training neural channel decoders have typically used the binary cross-entropy as the loss function for supervised learning. The cross-entropy loss is indeed an appropriate loss function for training a binary classifier. However, error correction is not a simple binary classification problem but rather a structured prediction problem, since the bits to be predicted are related to each other through the code structure. We therefore hypothesize that decoder training can be improved by incorporating knowledge of the code structure into the loss function.
To test this hypothesis, we introduce a new loss function, the syndrome loss, which penalizes the decoder for producing outputs that do not correspond to valid codewords. We show that combining the syndrome loss with the cross-entropy loss improves the frame error rate of several neural channel decoders for short block codes across all signal-to-noise ratios.
Perhaps more interestingly, the syndrome loss is completely unsupervised: that is, the decoder does not require knowledge of the transmitted codeword in order to compute the loss. Unsupervised learning could enable online training of decoders without the use of pilot signals, a useful property for receivers that must adapt quickly to changing channel conditions [18]. We show that, while taking care not to overfit to the training codewords, decoders can indeed be trained using only unsupervised learning.
In the rest of the paper, we define the syndrome loss, relate it to previous work, and show how it may be useful using a set of supervised and unsupervised learning experiments.

II. THE SYNDROME LOSS
In this work, we consider communication systems that use a binary linear code to transmit over an additive white Gaussian noise (AWGN) channel, although our method could potentially be applied to other types of channel. The transmitter encodes a k-bit message u ∈ GF(2) k using a generator matrix G ∈ GF(2) n×k to obtain an n-bit codeword c = Gu ∈ GF(2) n . The codeword is put in a bipolar format x = 1 − 2c ∈ {−1, +1} n and transmitted over the channel. The receiver receives a noisy signal y = x + w ∈ R n , where w ∈ R n is a vector of AWGN channel noise with variance σ 2 . The decoder must estimate x from y. We consider decoders that produce a soft output s ∈ R n , where the estimated bipolar codeword is found by taking the hard decisionx = sign(s), and the corresponding estimated binary codeword isĉ = 0.5 − 0.5x.
A linear code can be described by a parity-check matrix H ∈ GF(2) (n−k)×n . For example, the following is a paritycheck matrix for the (7,4)-Hamming code: The product Hĉ ∈ GF(2) n−k is called the syndrome. Ifĉ is a codeword, the syndrome will contain only 0; otherwise, the syndrome will contain at least a single 1. The syndrome can therefore be used to check if the decoder has successfully produced a valid codeword as an output.
Since adding numbers in GF (2) is equivalent to multiplying numbers in {−1, +1}, the syndrome can be expressed equivalently in the bipolar format in terms of the soft output s as follows: where M(i) is the set of columns in the ith row of H equal to 1.
One could imagine training a decoder to produce outputs that are codewords by minimizing the number of entries of the syndrome equal to −1. However, the syndrome is not well suited for conventional gradient-based learning, since the gradient of each entry is 0 almost everywhere. Accordingly, we introduce the "soft syndrome", a relaxation of the usual "hard syndrome". The soft syndrome is defined as follows: Note that this is just the check node equation from min-sum decoding, which has a non-trivial gradient (c.f. Chapter 5 of [19]).
As an example illustrating the behavior of the soft syndrome, suppose that the transmitter using the (7,4)-Hamming code sends the all-zeros codeword, We can construct a loss function, the syndrome loss, based on the soft syndrome that penalizes all the entries that are negative as follows: The usual supervised binary classification loss function is the cross-entropy loss: where g(·) is the logistic sigmoid function.
We propose to combine the syndrome loss with the crossentropy loss to obtain a complete loss function: ℓ total (c, s) = (1 − λ) · ℓ syndrome (s) + λ · ℓ cross-entropy (c, s), (10) where λ ∈ [0, 1]. When λ = 1, the loss is just the usual supervised loss; when 0 < λ < 1, the loss is supervised with the syndrome loss as a regularization term; when λ = 0, there is no dependence on the transmitted codeword, so the loss is unsupervised.

III. RELATED WORK
Other papers have proposed the use of something like the syndrome loss for decoding applications. In [20], the authors interpreted an iterative decoding algorithm as a gradient descent-based algorithm for minimizing a "generalized syndrome weight". This generalized syndrome weight was also treated in [21] and [22] in a similar way. In [23] and [24], Xia and Wu approached the problem of blind detection and identification of LDPC codes using "syndrome LLRs" for each candidate code.
It is important to distinguish our syndrome-based training method from that of [25], in which the syndrome is calculated from the received signal and used as part of the input to a neural network decoder. In our method, the decoder can take on any form, as long as the output is a soft estimate of the transmitted codeword. Thus, our method is not suitable for decoders in which the output is an estimate of the original message u, such as the polar decoder of [8].

IV. SUPERVISED LEARNING EXPERIMENTS
We trained neural normalized min-sum (NNMS) decoders [13] for four short block codes: a (63, 45) BCH code, a (16,8) LDPC code, a (128,64) polar code, and a (200,100) LDPC code. For all experiments described in this paper, we used the Adam update rule [26] with a learning rate of 0.01, and trained on 10,000 minibatches of 120 codewords each, with added noise drawn uniformly from all signal-to-noise ratios (SNRs). The all-zeros codeword was used during training, and random codewords were used during testing. We used the "multi-loss" approach proposed in [10]: the loss is computed for the soft output of every decoding iteration and these losses are summed to obtain the final loss. We measured the frame error rate (FER) of the decoders using Monte Carlo simulation, requiring a minimum of 100 frame errors to be detected and at least 100,000 frames for each SNR to be simulated to minimize the variance of the FER estimates. The hyperparameter λ was set to either 1 (purely supervised) or 0.5 (supervised + regularized). Slightly better results can be obtained by tuning the value of λ; we have not attempted this here to show that the syndrome loss works even without careful tuning. The performance of the decoders is shown in Fig. 1, 2, 3, and 4. The performance for decoders without learning (i.e., all weights are equal to 1) is also shown for comparison. It can be seen that the decoders trained with the syndrome loss have a small but consistent improvement in FER across all signalto-noise ratios. Thus, using the syndrome loss, decoders can be obtained with better FER performance at no additional cost during inference and little additional cost during training. The impact of the syndrome loss on bit error rate (BER), however, is less consistent. In some instances, we have found that BER is improved, and in others BER is made worse. It may be that the decoder attempts to output a valid codeword at the expense of making more bit errors.

V. UNSUPERVISED LEARNING EXPERIMENTS
We attempted to train decoders using purely unsupervised learning, i.e. with λ = 0. In some instances, training the decoder with λ = 0 led to the decoder having FER ≈ 1 across all SNRs. In these instances, because the decoder was trained using only the all-zeros codeword, it was able to find a set of positive and negative weights which, when multiplied with the all-zeros codeword, yield a valid (but incorrect) codeword. Two techniques were found to prevent this failure mode: 1) constraining the weights to being positive, e.g. using the softplus function (since we have observed that the weights are generally all positive after supervised learning), or 2) training using random codewords instead of the all-zeros codeword. The latter technique is preferable, since in theory some of the weights could be negative for the optimal parameter setting. The performance of an NNMS decoder for the (63, 36) BCH code trained on random codewords with λ = 0 is shown in Fig.  5. The performance of the decoder with unsupervised learning is better than the decoder without learning, suggesting that the syndrome loss could potentially be used for online learning in  decoders when the transmitted codewords are unknown. While the syndrome loss does teach the decoder about the structure of the code, in principle there is no guarantee that this will help the decoder learn to decode. For example, a decoder that simply outputs a random codeword independent of the received signal would incur no syndrome loss. Therefore, some prior information about the goal of decoding must be provided to the decoder. For a neural belief propagation decoder, this information is built into the network through the graphical model of the code. For a tabula rasa neural network, the prior information must be supplied in some other way, such as pre-training the model using supervised learning. We have not attempted to train an unconstrained neural network using the syndrome loss; we leave this for future work.

VI. CONCLUSION
In this paper, we introduced the syndrome loss, a new loss function for neural error-correcting decoders. The syndrome loss is designed to teach decoders to produce outputs with a correct structure. Decoders trained using the syndrome loss have consistently lower frame error rate when the syndrome loss is used as a regularization term and are capable of purely unsupervised learning when the appropriate precautions are taken.
ACKNOWLEDGMENT Thanks to Ali Hashemi for providing the parity-check matrix for the polar code used in our experiments.