OPINION
{1} Defendant was convicted of driving a vehicle while under the influence of liquor or drugs (DWI). He was adjudged a felon, and sentenced to an enhanced mandatory prison term after the State established at the sentencing hearing that he had four prior DWI convictions. Defendant finished serving the prison term imposed, and he was on probation when the State attempted to reimprison *225him and enhance his sentence again because it had recently discovered an additional prior DWI conviction. The trial court denied the State’s motion, and the State appeals.
{2} We conclude that all prior DWI offenses which could be used to enhance Defendant’s DWI sentence had to be proved by the State at the sentencing hearing. Therefore, the felony DWI sentence resulting from that hearing was not illegal or improper. Moreover, Defendant had a reasonable expectation of finality in that sentence such that further increasing it after he was released from prison could violate double jeopardy and due process. Accordingly, we affirm the order of the trial court denying the State’s motion to increase the felony DWI sentence originally given to Defendant.
BACKGROUND
{3} A defendant who has prior DWI convictions may be adjudged guilty of a felony and thereby subject to a mandatory prison term under NMSA 1978, Section 66-8-102 (2005). Subsection (H) directs that “[ujpon a fifth conviction ... an offender is guilty of a fourth degree felony and ... shall be sentenced to a term of imprisonment of two years, one year of which shall not be suspended, deferred or taken under advisement.” Subsection (I) then states that “[ujpon a sixth conviction ... an offender is guilty of a third degree felony and ... shall be sentenced to a term of imprisonment of thirty months, eighteen months of which shall not be suspended, deferred or taken under advisement.” Subsection (J) contains directions for seventh or subsequent DWI convictions that are not applicable here. The dispute in this case is whether the enhancement under Subsection (H) for a fourth degree felony with a mandatory prison term of one year or the enhancement under Subsection (I) for a third degree felony with a mandatory prison term of eighteen months is applicable.
{4} The indictment charged Defendant with DWI, and alleged that Defendant was subject to a felony DWI sentence because of prior DWI convictions. Defendant was then found guilty of DWI by a jury. Prior to the sentencing hearing, the State alleged that six prior DWI convictions were applicable to Defendant’s sentence. At the sentencing hearing, the trial court determined that there was insufficient proof that two of the alleged pri- or DWIs could be used to enhance Defendant’s sentence and concluded that four prior DWI convictions would be used in sentencing Defendant. The State’s request for a continuance to obtain further proof relating to the two disputed prior DWIs was denied. Therefore, the trial court concluded that this was Defendant’s fifth DWI conviction for sentencing purposes. Consistent with Subsection (H), the trial court imposed a two-year prison term, required Defendant to serve the one-year mandatory term, suspended the second year, and placed Defendant on five years of probation.
{5} When Defendant had approximately two months remaining to be served in prison, the State filed a motion denominated as a “Motion to Correct Illegal Sentence.” The motion recited that the State had “recently” learned of another DWI conviction, and asserted that Defendant’s sentence should therefore be changed to reflect a sixth DWI conviction. This would result in elevating Defendant’s conviction from a fourth degree felony to a third degree felony, and increasing the mandatory prison term from one year to eighteen months as required by Subsection (I). When the State’s motion was heard, Defendant had completed serving his prison term, and he was serving his probation. The State argued that because Defendant’s sentence would not be complete until he finished serving his probation, his original sentence was subject to being increased, and double jeopardy was not implicated. Defendant argued that the State had the burden of proving all prior convictions at the time of sentencing, that he had a right to finality in the sentence he received, and that increasing his sentence at that time was unfair and would violate his constitutional right to be free from double jeopardy.
{6} The trial court filed a written order denying the State’s motion, finding that Defendant’s original sentence was not illegal and that while it had discretion to increase Defendant’s original sentence on the basis of the DWI conviction discovered after sentence was originally imposed, it would not exercise *226its jurisdiction to reopen the sentence because Defendant had already completed serving his prison term. The State appeals from this order.
ANALYSIS
{7} The question presented in this appeal is whether the trial court was required to further increase Defendant’s original felony DWI sentence when a prior DWI conviction is discovered by the State after the original sentence was imposed and Defendant has completed serving the term of imprisonment, but has not completed probation. While New Mexico courts have addressed this question in the context of habitual offender enhancement, the question of whether the same rule applies to increased punishment for repeat DWI offenders under Section 66-8-102 is an issue of first impression. Resolution of this issue requires us to interpret the sentencing provisions of Section 66-8-102. We are therefore presented with a question of law, and our review is de novo. See State v. Coyazo, 2001-NMCA-018, ¶ 5, 130 N.M. 428, 25 P.3d 267 (stating that whether an enhanced felony DWI sentence was subject to an additional habitual offender enhancement required statutory interpretation, a question of law subject to de novo review); State v. Guerra, 2001-NMCA-031, ¶ 6, 130 N.M. 302, 24 P.3d 334 (stating that the power of a trial court to sentence is derived exclusively from statute and issues of statutory construction and interpretation are questions of law which are reviewed de novo).
{8} Defendant’s original felony sentence was not illegal or improper; it was a valid sentence when it was imposed, and therefore subject to the general prohibition against being increased once he started serving it. “It is a well-established principle of New Mexico law that a trial court generally cannot increase a valid sentence once a defendant begins serving that sentence.” State v. Porras, 1999-NMCA-016, ¶ 7, 126 N.M. 628, 973 P.2d 880. A limited exception is when the original sentence is illegal or improper. Id. The State seeks to avoid application of this rule, making two arguments.
{9} The State first asserts that the reasoning applicable to habitual offender enhancements, where a habitual offender’s sentence may be enhanced at any time before the underlying prison term, period of probation, or period of parole expires also applies to enhanced DWI sentencing. See id. ¶ 8 (“A defendant’s sentence may be enhanced as a habitual offender at any time prior to the expiration of the underlying sentence or period of parole.”). It first argues that there is nothing in the DWI statute that expressly forbids the sentencing court from imposing an additional enhancement once a defendant has begun serving his sentence. Furthermore, it argues, DWI sentencing and habitual offender enhancement proceedings are alike because enhanced sentences are mandatory under both statutes upon proof of prior convictions, and the sentencing court is not given discretion to ignore the proven prior convictions.
{10} We reject the State’s argument because it overlooks two critical key features of habitual offender enhancement that distinguish it from DWI sentencing. First, the habitual offender statute expressly grants the sentencing court jurisdiction to enhance a defendant’s sentence after a defendant has started serving his original sentence, but the DWI sentencing statute does not. Second, the sentencing on the underlying charge and the enhancement of that sentence for habitual offenders involve two separate proceedings, but DWI sentencing involves only one proceeding.
{11} The habitual offender statute clearly grants the sentencing court jurisdiction to adjudicate a charge of habitual offender status after a defendant has started serving the original sentence imposed for the underlying charges. NMSA 1978, Section 31-18-19 (1977) directs:
If at any time, either after sentence or conviction, it appears that a person convicted of a noncapital felony is or may be a habitual offender, it is the duty of the district attorney of the district in which the present conviction was obtained to file an information charging that person as a habitual offender.
NMSA 1978, Section 31-18-18 (1977) also imposes a duty on prison, probation, and parole officers. If they learn that a “person *227charged with or convicted of a noncapital felony” is a habitual offender they are required to report the facts to the district attorney “who shall then file an information.” Id. NMSA 1978, Section 31-18-20(A) (1983) then directs the court in which the defendant was originally convicted to bring before it a person charged as a habitual offender “whether he is confined in prison or not,” and conduct a hearing to determine if he is a habitual offender, and if he is, “the court shall sentence him to the punishment as prescribed.” Section 31-18-20(C). Given these broad statutory mandates, we have observed that “[t]he trial court’s jurisdiction seems to be of indefinite duration” limited only by the constitutional prohibition against double jeopardy. State v. Roybal, 120 N.M. 507, 510, 903 P.2d 249, 252 (Ct.App.1995). In this context, once a defendant has completely served his sentence, his punishment for the crime has come to an end, and double jeopardy forbids enhancing the sentence. Id.
{12} The DWI sentencing statute is significantly different. Unlike the habitual offender statutes, Section 66-8-102 does not expressly grant a trial court jurisdiction to increase a defendant’s DWI sentence after he has started serving the original sentence. On the contrary, Section 66-8-102 provides in Subsections (G), (H), (I), and (J) that the enhanced sentence is to be imposed “upon conviction.” This is a statutory directive to the State to present all of its evidence of any prior DWIs when a defendant appears for sentencing on the DWI conviction. Further, this statutory sentencing structure does not allow for an additional enhancement to be imposed after an enhanced sentence is imposed. “Statutes authorizing a more severe punishment as conviction for a second offense are deemed highly penal and therefore must be strictly construed.” State v. Keith, 102 N.M. 462, 465, 697 P.2d 145, 148 (Ct.App.1985). Moreover, to the extent there is any doubt in the statute concerning when proceedings to increase the original sentence may be brought, that doubt must be resolved in Defendant’s favor under the rule of lenity. Id.; see State v. Russell, 113 N.M. 121, 124, 823 P.2d 921, 924 (Ct.App.1991) (quoting and applying Keith). Our Supreme Court applied these same propositions to enhanced felony DWI sentencing in State v. Anaya, 1997-NMSC-010, ¶ 30, 123 N.M. 14, 933 P.2d 223, which quoted Swafford v. State, 112 N.M. 3, 16, 810 P.2d 1223, 1236 (1991) as follows: “ ‘When it cannot be said with certainty that the legislature intended to authorize the imposition of an enhanced sentence under particular circumstances ... we presume that the legislature did not so intend.’ ” Anaya, 1997-NMSC-010, ¶ 30, 123 N.M. 14, 933 P.2d 223.
{13} The second reason a court has authority to enhance a habitual offender’s sentence after the offender has started serving the original sentence is that habitual offender enhancement proceedings are separate from the sentencing proceeding for the underlying charges. As already noted, a habitual offender proceeding is initiated by the filing of a criminal information, followed by a hearing. This denotes a proceeding that is separate from those relating to the underlying charges. In this regard, we have specifically stated, “the proceedings involving the underlying charges and the proceedings involving the habitual offender charges are separate in New Mexico.” Porras, 1999—NMCA-016, ¶ 11, 126 N.M. 628, 973 P.2d 880. “An unenhanced sentence remains a valid sentence until it is determined that defendant is a habitual offender and that the underlying sentence is subject to enhancement.” State v. Gaddy, 110 N.M. 120, 122, 792 P.2d 1163, 1165 (Ct.App.1990). Up to the point that a defendant is proved to be a habitual offender, “anything could happen in the habitual proceedings — the state could decide not to pursue them, or fail to prove its case.” Id. at 123, 792 P.2d at 1166. However, once the separate habitual offender proceeding results in a determination that a defendant is a habitual offender, the sentence originally imposed for the underlying offense is “no longer an authorized sentence because supplanted by the enhanced sentence mandated for an habitual offender.” State v. Harris, 101 N.M. 12, 15, 677 P.2d 625, 628 (Ct.App.1984).
{14} To illustrate, in Porras, the defendant was originally given a sentence of ninety days incarceration, which he immediately started serving. 1999-NMCA-016, ¶ 3, 126 *228N.M. 628, 973 P.2d 880. He was subsequently proved to be a habitual offender, and the trial court increased the underlying, original ninety-day sentence to three years, and imposed an additional eight-year habitual offender enhancement for a total prison term of eleven years. Id. ¶¶ 4-5. On appeal, the defendant did not contest the eight-year habitual offender enhancement; he only contested the jurisdiction of the trial court to increase the underlying sentence from ninety days to three years. Id. ¶ 12. We held that the defendant had an expectation of finality in the original sentence for the underlying charges once he began to serve it, and concluded that while the State could seek to enhance the defendant’s sentence in a separate proceeding under the habitual offender statute, this had no effect on the original sentence imposed for the underlying charges. Id. ¶¶ 11-12. Increasing the underlying sentence once the defendant started serving it violated the defendant’s double jeopardy rights protected by both the United States and New Mexico Constitutions. Id. ¶ 1. Thus, there are two separate proceedings with two separate consequences. In the underlying case once a valid sentence is imposed and the defendant begins serving that sentence, the court has no jurisdiction to increase it. In the separate habitual offender proceeding, the original sentence as originally imposed is subject to being enhanced. “[T]here is no doubt that the original sentence is subject to enhancement after the defendant has begun serving it and before he has been discharged from custody.” March v. State, 109 N.M. 110, 112, 782 P.2d 82, 84 (1989) (emphasis added).
{15} On the other hand, sentencing for DWI does not entail a proceeding that is separate and apart from the DWI case itself. In Anaya, 1997-NMSC-010, ¶ 18, 123 N.M. 14, 933 P.2d 223, our Supreme Court concluded that when the legislature created felony DWI based on prior DWI convictions it did not change the elements of the offense itself, and a jury is not required to determine if a felony sentence is applicable based on the number of prior DWI convictions. Id. ¶ 19. While a bifurcated trial is provided for in other states, so that the jury decides whether the defendant committed the charged DWI offense before hearing evidence of prior convictions, id., “our legislature has made no express provision for a bifurcated proceeding.” Id. We have also noted that while the basic elements of a DWI offense have not changed, the punishment has, and when the DWI offense is proved, “[sentencing is thereafter set by and tied to the number of times an offender has been convicted of the offense.” State v. Hernandez, 2001-NMCA-057, ¶ 23, 130 N.M. 698, 30 P.3d 387. “Habitual offender enhancements, on the other hand, despite the mandatory tone of the statute, are not automatically included in any sentence imposed on a defendant.” Gaddy, 110 N.M. at 123, 792 P.2d at 1166. Finally, “DWI sentences based on repeat convictions do not impose a separate sentence on top of a basic sentence [as occurs for a habitual offender enhancement]. Instead, repetition of offense is accounted for by increasing the basic punishment per numbered conviction.” Hernandez, 2001-NMCA-057, ¶ 30, 130 N.M. 698, 30 P.3d 387. These differences, coupled with the statutory mandate that a felony DWI sentence based upon prior convictions is to be imposed “upon conviction,” persuade us that the same logic applicable to habitual offender proceedings does not apply here.
{16} The State’s second argument is that apart from the rationale applicable to habitual offender proceedings, the construction placed upon the statutory enhancement for armed robbery in State v. Stout, 96 N.M. 29, 627 P.2d 871 (1981), allows Defendant’s sentence to be increased in this case. The armed robbery statute provides in pertinent part: ‘Whoever commits robbery while armed with a deadly weapon is, for the first offense, guilty of a second degree felony and, for second and subsequent offenses, is guilty of a first degree felony.” NMSA 1978, § 30-16-2 (1973). In Stout, the defendant was convicted of robbery with a firearm and sentenced as a first offender to a prison term of not less than fifteen nor more than fifty-five years. 96 N.M. at 31, 627 P.2d at 873. Eight months after he began serving his sentence, the State filed an information alleging the defendant had previously been convicted of armed robbery, and that he should *229therefore be sentenced to life imprisonment in accordance with Section 30-16-2. Stout, 96 N.M. at 31, 627 P.2d at 873. Following a trial on the supplemental information in which a jury determined that the defendant was previously convicted of armed robbery as alleged, the trial court vacated the original sentence and sentenced the defendant to life imprisonment. Id. After noting that the defendant had served only eight months of his sentence before the enhanced sentence was sought, our Supreme Court approved of this procedure, stating, “[w]e hold that the defendant’s initial sentence was the valid and appropriate sentence until it was proven that he was a prior offender under the appropriate enhancement statute.” Id. at 32, 627 P.2d at 874 (emphasis added). Our Supreme Court subsequently decided Anaya, in which it concluded that the elements of DWI do not change, whether it is a first or subsequent offense, as in Stout, where the elements of armed robbery are the same, whether it is a first or subsequent offense. Anaya, 1997-NMSC-010, ¶¶ 20-21, 123 N.M. 14, 933 P.2d 223. “The armed robbery statute at issue in Stout was similar to New Mexico’s DWI statute in that it provided both for a higher degree of offense and a more severe penalty for repeated violations.” Id. ¶ 21. The State therefore argues that by analogy, there is no bar to the State seeking to increase Defendant’s DWI sentence in this case. We disagree.
{17} The statute and facts in Stout are materially different from those in this case. A time is specified for imposing an enhanced sentence under the DWI sentencing statute: the enhanced sentence is to be imposed “upon conviction.” On the other hand, no such time is specified under the armed robbery enhancement statute: the enhanced sentence is imposed “for second and subsequent offenses.” The State’s argument also overlooks the fact that in this case, the sentencing hearing based on Defendant’s prior DWIs was already held and that Defendant not only started serving the increased sentence which resulted from that hearing, he completed serving the prison term imposed. The State now seeks to further increase Defendant’s sentence. That is clearly not what occurred in Stout, where there was only one hearing to enhance the defendant’s sentence, and one enhanced sentence imposed. Finally, the defendant had only served eight months of a prison term of not less than fifteen nor more than fifty-five years when the underlying sentence was enhanced in Stout, whereas in this case, Defendant had already completed serving his enhanced prison term when the State attempted to reimprison him and again enhance his sentence.
{18} We therefore conclude that the original felony sentence imposed upon Defendant based on five DWI convictions was a valid sentence. A contested hearing to determine how many DWI convictions Defendant had was held. To the extent the court could have sentenced Defendant based upon six DWI convictions, it was the State’s burden to present proof of those convictions at the sentencing hearing. See State v. Gaede, 2000-NMCA-004, ¶ 8, 128 N.M. 559, 994 P.2d 1177 (“[T]he State bears the initial burden of presenting evidence of the validity of each of [a defendant’s] prior convictions.”). Once the hearing was concluded, the trial court imposed the prison term provided by Section 66-8-102. See State v. McDonald, 113 N.M. 305, 307, 825 P.2d 238, 240 (Ct.App.1991) (stating that a sentence authorized by law constitutes a legal sentence); see also State v. Baros, 78 N.M. 623, 625, 435 P.2d 1005, 1007 (1968) (“This court has held that sentences must be imposed as prescribed by statute.”).
{19} We conclude by noting that the State’s arguments overlook Stout’s recognition that fundamental fairness and due process concerns may prohibit enhancing a sentence. “[W]e assume that in some case it could violate the defendant’s rights to wait a substantial period of time before enhancement is sought[.]” Id. at 32, 627 P.2d at 874. Stout thus aligns itself with cases acknowledging that due process may be denied by enhancing a sentence that is substantially or fully served. Breest v. Helgemoe, 579 F.2d 95, 101 (1st Cir.1978), states that the power to correct a sentence, even one that is statutorily invalid, is subject to some temporal limit under principles of fundamental fairness. Id. Thus, due process may be denied *230when a defendant has already served so much of the original sentence imposed that “his expectations as to its finality have crystallized and it would be fundamentally unfair to defeat them.” United States v. Lundien, 769 F.2d 981, 987 (4th Cir.1985). For example, in DeWitt v. Ventetoulo, 6 F.3d 32 (1st Cir.1993), after the state released the defendant from prison, and he had served eight months of parole, his sentence was increased to conform with state law, and he was ordered reimprisoned. Id. at 33. The defendant had obtained work, and resumed his relationship with family members and his girlfriend while on parole. Id. Concluding he was denied due process, the United States District Court granted the defendant a writ of habeas corpus, and the First Circuit Court affirmed. Id. at 34, 37. In concluding that the line of fundamental fairness was crossed, the court considered various factors, including the reasonableness of the defendant’s reliance on the sentence he received, his release from prison and formation of new roots, and the tardiness of the state in seeking to correct the error. Id. at 36.
{20} In State v. Hardesty, 129 Wash.2d 303, 915 P.2d 1080 (1996) (en banc), the state and the defendant entered into a plea agreement that contained an agreed criminal history revealing two prior felonies. Id. at 1082. Based on the plea and criminal history, the defendant was sentenced to fourteen months in prison, and he was released after serving approximately nine months. Id. After the defendant was released, the state fortuitously discovered that the defendant had two additional prior felony convictions, which had not been entered on a national computer base when the original plea agreement was made. Id. at 1082-83. The state therefore filed a motion requesting that the defendant be re-sentenced to twenty-nine months imprisonment based on the additional felonies. Id. at 1082. While acknowledging that United States v. DiFrancesco, 449 U.S. 117, 121, 101 S.Ct. 426, 66 L.Ed.2d 328 (1980), rejected a per se rule against increasing an erroneous sentence under the double jeopardy clause, the Court also recognized that the double jeopardy clause continues to play a role, albeit limited, in sentencing proceedings:
In an ordinary sentencing proceeding to correct an erroneous sentence, the analytical touchstone for double jeopardy is the defendant’s legitimate expectation of finality in the sentence, which may be influenced by many factors such as the completion of the sentence, the passage of time, the pendency of an appeal or review of the sentencing determination, or the defendant’s misconduct in obtaining the sentence.
Hardesty, 915 P.2d at 1085. The court concluded that a defendant acquires a legitimate expectation of finality in a sentence that is substantially or fully served unless he is on notice the sentence may be modified, due to either a pending appeal or the defendant’s own fraud in obtaining the sentence. Id. The enhanced sentence was therefore vacated because the court concluded that the state failed to prove that the defendant committed fraud upon the state when he originally made the plea agreement. Id. at 1088-89.
{21} Further enhancing Defendant’s sentence in this case would violate the fundamental fairness and due process concerns expressed in Stout. The State had its opportunity to prove what sentence was appropriate at the sentencing hearing. The State was able to prove that four prior DWI convictions were applicable, the appropriate enhanced felony sentence was imposed, and Defendant started serving his prison term. When Defendant had only about two months remaining to be served in prison, the State sought an additional six month term of imprisonment based on an additional prior DWI conviction it “recently” learned about. The State’s motion was then heard after Defendant had completed serving the prison sentence imposed, and he was out of prison serving five years of probation.
CONCLUSION
{22} We hold that Defendant received a legal sentence as a result of the sentencing hearing at which the State alleged that Defendant had prior DWIs. Further, he had a reasonable expectation of finality in the *231length and structure of the enhanced sentence that was imposed, and once Defendant completed serving that prison sentence, the trial court was within its discretion in ruling that due process prohibited the sentence from being further increased because of the additional DWI conviction that was subsequently discovered. We affirm the trial court order denying the State’s “Motion to Correct Illegal Sentence.”
{23} IT IS SO ORDERED.
WE CONCUR: LYNN PICKARD and CYNTHIA A. FRY, Judges.